Strongly Connected Components — Kosaraju's Algorithm

DiffPush Tier Graphs · Other Algorithms O(V + E) · O(V + E)

Counting the Closed Courier Loops

A courier's one-way route map hides closed guilds: sets of hubs where every hub can reach every other by following the arrows. Management wants the number of such mutually-reachable guilds. Two passes do it — log when each hub finishes its exploration, then replay the map with every arrow reversed, popping hubs in decreasing finish order and counting each fresh exploration as one guild.

Input: An integer V (vertices 0..V-1) and an adjacency list adj where adj[i] lists the destinations of vertex i's one-way edges.

Output: Return the number of strongly connected components.

Constraints

1 <= V <= 10^5
0 <= number of edges <= 2 * 10^5

Examples

Example 1

Input: {"V":5,"adj":[[1],[2],[0,3],[4],[]]}
Output: 3
0, 1, 2 cycle among themselves; 3 and 4 stand outside as singletons.

Example 2

Input: {"V":4,"adj":[[1],[2],[3],[0]]}
Output: 1
A single grand cycle makes all four vertices one component.

Solve this in your browser →

Also on LeetCode ↗