# Strongly connected components P90865

Statement

html

A directed graph G = (V, A) consists of a set of vertices V and a set of arcs A. An arc is an ordered pair (u, v), where u, vV. A path from a vertex vi1 to a vertex vik is a sequence of arcs (vi1, v12), (vi2, vi3), …, (vik−1, vik). By definition, there is always a path from every vertex to itself.

Consider the following equivalence relation: two vertices u and v of G are related if, and only if, there is a path from u to v and a path from v to u. Every equivalence class resulting from this definition is called a strongly connected component of G.

Given a directed graph, calculate how many strongly connected components it has.

Input

Input begins with the number of cases. Each case consists of the number of vertices n and the number of arcs m, followed by m pairs (u, v). Vertices are numbered starting at 0. There are not repeated arcs, nor self-arcs (v, v). Assume 1 ≤ n ≤ 104.

Output

For every graph, print its number of strongly connected components.

Public test cases
• Input

```3

3 3
0 1  1 2  2 0

7 7
0 1  1 2  2 0  3 4  4 6  6 3  0 6

6 7
0 1  0 2  1 3  2 3  3 4  4 2  5 4
```

Output

```Graph #1 has 1 strongly connected component(s).
Graph #2 has 3 strongly connected component(s).
Graph #3 has 4 strongly connected component(s).
```
• Information
Author
Xavier Martínez
Language
English
Official solutions
C++ Python
User solutions
C++ Python
Event
Quart Concurs de Programació de la UPC - Semifinal
Date
2006-09-20