Strongly connected components P90865
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, v ∈ V. 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.
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).
- Author
- Xavier Martínez
- Language
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python