192. Count Strongly Connected Components

Given a directed graph with n vertices and m edges, count the number of strongly connected components - maximal groups of vertices where every vertex in the group can reach every other vertex in the group.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers u v, a directed edge. Output: Print a single integer - the number of strongly connected components.

1 <= n <= 10^5

Every vertex belongs to EXACTLY ONE strongly connected component, even an isolated vertex with no edges at all - it's trivially strongly connected to itself, forming its own singleton SCC.

Count the maximal groups of vertices in a directed graph where every vertex can reach every other vertex within the same group. Brute force: Check every pair of vertices directly for mutual reachability (both u to v and v to u) - this costs O(n² * (n+m)), far too slow for larger graphs, when Kosaraju's two-pass DFS technique finds all SCCs in linear time. Optimised: The clever insight behind Kosaraju's algorithm is that processing vertices in REVERSE FINISH ORDER on the REVERSED graph guarantees each DFS tree formed in the second pass exactly captures one strongly connected component - a genuinely elegant reduction that avoids ever needing pairwise reachability checks.

Run a single DFS maintaining each vertex's discovery time and a low-link value, the smallest discovery time reachable from its subtree including through back edges to vertices still marked 'on stack' on an explicit stack. Whenever a vertex's low-link equals its own discovery time, pop that explicit stack down to and including that vertex, and everything popped forms one strongly connected component. This finds all SCCs in a single DFS pass with no need to build a transpose graph at all. Time: O(n+m) Space: O(n+m)

For each vertex v, run a forward BFS or DFS from v to find every vertex it can reach, and a backward BFS or DFS, traversing edges in reverse, to find every vertex that can reach v; the intersection of these two sets is exactly v's strongly connected component, since mutual reachability in both directions is precisely what defines an SCC. Doing this independently for every vertex and merging matching components correctly finds all SCCs, but it repeats a full pair of graph traversals for every single vertex. Time: O(n*(n+m)) Space: O(n^2)

Run one DFS on the original graph, pushing each vertex onto a stack when it finishes; build the transpose graph with all edges reversed; then repeatedly pop vertices off the stack and, for each one not yet visited, run a DFS on the transpose graph, where every resulting DFS tree is exactly one strongly connected component. This needs only two full graph passes total instead of one pair per vertex, at the cost of explicitly constructing and storing the transpose graph. Time: O(n+m) Space: O(n+m)

1. Use KOSARAJU'S algorithm: do a DFS on the original graph, recording each vertex's FINISH order (when its DFS call fully completes). 2. Build the REVERSED graph (every edge flipped), then DFS it processing vertices in REVERSE finish order from the first pass. 3. Each separate DFS tree formed in this SECOND pass is exactly ONE strongly connected component.

Time: O(n + m) - two DFS passes (one on the original graph, one on the reversed graph), each linear. Space: O(n + m), for the original graph, its reverse, and the finish-order tracking.

Test an isolated vertex with no edges (it forms its own SCC), a graph that is entirely one SCC (answer 1), and n at the upper bound of 10^5.

Be ready to mention Tarjan's algorithm as an equally valid, single-pass alternative (using discovery times and low-link values, similar to bridge-finding) - both Kosaraju's and Tarjan's find SCCs in O(n+m), just via different mechanics.