Strongly Connected Component Problems
3 Strongly Connected Component LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Group directed vertices that can reach one another
A strongly connected component is a maximal set of vertices with directed paths in both directions between every pair. Collapsing these groups produces a directed acyclic graph. This differs from ordinary undirected connectivity: always check the actual problem statement, since catalogue tags do not guarantee that every linked problem needs an SCC algorithm.
When to use it
Use Tarjan's or Kosaraju's algorithm when directed cycles must be grouped before reasoning about dependencies or reachability. For an undirected island, tree, or spanning-tree question, flood fill, articulation points, or disjoint-set union may be the relevant technique instead.
Worked example
Edges: A→B, B→C, C→A, C→D, D→E, E→D.
- A, B, and C lie on a directed cycle, so each can reach the other two.
- D and E can reach each other. There is a path from C to D, but no path from D or E back to A.
- Collapse the two groups into component vertices. The only inter-component edge goes from {A, B, C} to {D, E}.
There are two SCCs: {A, B, C} and {D, E}. A one-way edge between them does not merge them.
Time and space
Tarjan and Kosaraju run in O(V + E) time. Tarjan uses O(V) auxiliary state beyond adjacency lists. Kosaraju commonly also stores a reversed graph, which requires O(V + E) additional representation space.
Mistakes to check
- In Tarjan's algorithm, an already visited neighbor affects the active-component low-link calculation only while it remains on the SCC stack.
- The SCC stack is not simply the recursion stack: a returned DFS call can still belong to an unfinished component.
- Run the traversal from every unvisited vertex. Component numbers depend on traversal order and should not be treated as stable identifiers.
Further reading: Boost Graph: strongly connected components
Guide reviewed .