Strongly Connected Pieces

Difficulty: 1800 4000 ms 128 MB

graphs scc

Count the strongly connected components of a directed graph (maximal sets where every node reaches every other).

Input: the first line has N and M; each of the next M lines has a directed edge u → v.

Output: the number of SCCs.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴

Sample Tests

5 5
1 2
2 3
3 1
3 4
4 5

3

3 0

3

Read the Editorial