Strongly connected components P90865


Statement
 

pdf   zip

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, 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.

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