Loading repovive.com/problems/classics/42
Given a directed graph with n vertices and m edges, find the number of strongly connected components (SCCs).
A strongly connected component is a maximal set of vertices such that there is a path from every vertex to every other vertex within the set.
5 6 1 2 2 3 3 1 3 4 4 5 5 4
Vertices 1, 2, and 3 form one SCC because they lie on the cycle 1 -> 2 -> 3 -> 1. Vertices 4 and 5 form another SCC because 4 reaches 5 and 5 reaches 4.
2
3 3 1 2 2 3 1 3
All edges go from a smaller-numbered vertex to a larger-numbered vertex. No two different vertices can reach each other both ways, so each vertex is its own SCC.
3
4 4 1 2 2 3 3 4 4 1
The edges form the cycle 1 -> 2 -> 3 -> 4 -> 1. Every vertex can reach every other vertex, so all four vertices are in one SCC.
1