Skip to content
Tutorials Center
My learning

Topics

Lesson 142 of 225 ยท Shortest Paths and Spanning Trees

Strongly Connected Components

Find strongly connected components in a directed graph with Kosaraju's two-pass DFS and Tarjan's low-link method, then build the condensation DAG in Python.

In an undirected graph, "connected component" is easy to define: the groups of vertices that can reach each other. With directed edges the question gets richer, because reaching is no longer symmetric. You can walk from page A to page B by following links, and still have no way back. The right notion is a strongly connected component (SCC): a maximal group of vertices in which every vertex can reach every other vertex by following edge directions.

SCCs reveal the cyclic cores of a directed graph. Mutually dependent modules, pages that can all lead to each other, groups of people who follow each other in a chain, states of a program that can return to one another. Collapse each SCC into a single node and what remains is always a DAG, which you can then process with topological order. This lesson shows two linear-time algorithms: Kosaraju's (simple, two passes) and Tarjan's (one pass, clever), and what to do with the result.

What an SCC looks like

Take this directed graph with 9 vertices:

TEXT
edges: 0->1  1->2  2->0   2->3   3->4  4->3   4->5   5->6  6->7  7->5   7->8   2->5

  {0, 1, 2}  --->  {3, 4}  --->  {5, 6, 7}  --->  {8}
      |                              ^
      +------------ 2 -> 5 ------------+

  inside each braces group every vertex reaches every other one

Reading it off:

  • 0, 1, 2 form a cycle, so each reaches the others: SCC {0, 1, 2}.
  • 3 and 4 point at each other: SCC {3, 4}.
  • 5, 6, 7 form another cycle: SCC {5, 6, 7}.
  • 8 can be reached but can never return: SCC {8} on its own. A vertex with no cycle through it is its own one-vertex SCC.

Every vertex belongs to exactly one SCC, because "mutually reachable" is an equivalence relation. Edges between different SCCs only go one way: {0,1,2} โ†’ {3,4} โ†’ {5,6,7} โ†’ {8}. If any edge went backward, the two components would merge into one.

Brute force: reachability both ways

Two vertices u and v are in the same SCC exactly when u reaches v and v reaches u. So run a BFS from every vertex to learn who it reaches, then group vertices that reach each other. That costs V searches of O(V + E) each, O(V ยท (V + E)), which is fine for a few thousand vertices and far too slow for a million. It is also a great correctness check for the fast algorithms.

Python Brute force: group vertices that reach each other

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Kosaraju's algorithm

Kosaraju's algorithm uses two depth-first searches and one idea: reversing all edges does not change which vertices are strongly connected (if u reaches v and v reaches u, that stays true when all arrows are flipped), but it does change which components can leak into which.

  1. Run DFS over the whole graph and record vertices in order of finishing time (when the DFS is done with a vertex and all its descendants).
  2. Build the transpose graph (every edge reversed).
  3. Process vertices in decreasing finishing time. Whenever you meet a vertex that is not assigned yet, run a DFS in the transpose graph from it. Everything that DFS reaches is one SCC.

Why does it work? The vertex that finishes last in step 1 sits in a "source" component of the condensation, one with no incoming edges from other components. In the transpose graph that component has no outgoing edges, so a DFS started there cannot escape; it collects exactly that component. Remove it and repeat: the next-latest finisher is again in a source component of what remains.

Python Kosaraju's algorithm step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the component numbers come out in topological order of the condensation: component 0 is the one with no incoming edges from other components, and so on. That is a free bonus of Kosaraju's method.

An iterative version for large graphs

Python's recursion limit is about a thousand frames, so the recursive DFS above fails on a graph shaped like a long chain. Real inputs often have 100,000 vertices. The cure is an explicit stack that remembers, for each vertex, how many of its neighbors we have already tried.

Python Iterative Kosaraju handles 5000-vertex chains

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A path has no cycles, so every vertex is its own SCC. Add one edge from the last vertex back to the first and the entire chain becomes a single SCC.

Tarjan's algorithm

Tarjan's algorithm finds all SCCs with one DFS and no transposed graph. It tracks two numbers for each vertex:

  • disc[v]: the discovery time, the order in which DFS first reached v.
  • low[v]: the smallest discovery time reachable from v's DFS subtree by following tree edges and at most one edge to a vertex that is still on the stack.

It keeps a stack of vertices that were visited but whose component has not been decided yet. When the DFS finishes a vertex v and finds low[v] == disc[v], then v cannot reach anything discovered before it, so v is the root of an SCC: pop the stack down to v, and those popped vertices are one component.

TEXT
low[v] = min( disc[v],
              low[child]      for tree edges v -> child,
              disc[w]         for edges v -> w where w is still on the stack )
Python Tarjan's algorithm with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The components appear in reverse topological order: the sink component {8} is complete first, and the source component {0, 1, 2} last. Kosaraju gives the opposite order. Both take O(V + E) time and O(V) space.

Watch out: the second branch of Tarjan's update must use disc[v] and only when v is on the stack. If v already belongs to a finished component, the edge points into another SCC and must be ignored. Using low[v] there, or skipping the stack check, merges components that should stay separate.

Kosaraju or Tarjan?

Kosaraju Tarjan
DFS passes two (plus building the transpose) one
Extra structures reversed adjacency lists disc, low, stack, on-stack flags
Output order topological order of the condensation reverse topological order
Time / space O(V + E) / O(V + E) O(V + E) / O(V)
Easiest to explain and remember run on a huge graph in one pass

Both are fine. Pick Kosaraju when you want the simplest code to reason about, Tarjan when memory matters or you want to avoid building the transpose.

The condensation DAG

If you replace every SCC by one node and keep one edge between components whenever any original edge connects them, you get the condensation graph. It always has no cycles; a cycle among components would merge them into one. This lets you attack problems on cyclic graphs by first collapsing the cycles, then using DAG techniques (topological order, DAG shortest and longest paths, DP in topological order).

A famous use: how many edges must you add to make the whole graph strongly connected? If the condensation has only one node, the answer is 0. Otherwise it is max(number of source components, number of sink components), where a source has no incoming edge and a sink has no outgoing edge.

Python Condensation DAG and edges needed to be strongly connected

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The graph has one source component {0, 1, 2} and one sink component {8}, so a single new edge from the sink back to the source (say, 8 โ†’ 0) makes the entire graph strongly connected.

Where SCCs are used

  • Dependency cycles. Build tools and package managers find groups of modules that depend on each other.
  • Compilers and program analysis. Mutually recursive functions form SCCs of the call graph; they must be analyzed together.
  • 2-SAT. A boolean formula with clauses of two literals is unsatisfiable exactly when some variable and its negation are in the same SCC of the implication graph.
  • Web and social graphs. The "core" of strongly linked pages or accounts.
  • Model checking and Markov chains. Recurrent classes are SCCs with no outgoing edges.

Common mistakes

  • Using undirected connected components. Ignoring edge direction merges vertices that cannot get back to each other.
  • Forgetting to transpose in Kosaraju's second pass, or processing vertices in increasing order instead of decreasing finishing time.
  • Mixing up low[v] and disc[v] in Tarjan's back-edge case, or ignoring the on-stack check.
  • Recursion depth. Both algorithms are DFS-based; a 100,000-vertex chain overflows the default Python limit. Use the iterative form.
  • Forgetting single-vertex components. A vertex with no cycle is its own SCC; count it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a directed graph, when are two vertices u and v in the same strongly connected component?

    Strong connectivity means mutual reachability: following edge directions, each reaches the other.
  2. 2. In Kosaraju's algorithm, in which order does the second DFS (on the transposed graph) start from vertices?

    The latest finisher lies in a source component of the original graph, which is a sink in the transpose, so the DFS cannot leak into other components.
  3. 3. In Tarjan's algorithm, when does a vertex v start a new component?

    If low[v] == disc[v], nothing in v's subtree can reach a vertex discovered before v, so v is the root of an SCC and the stack is popped down to v.
  4. 4. What is the time complexity of Kosaraju and Tarjan on a graph with V vertices and E edges?

    Each performs a constant number of DFS passes, and each vertex and edge is processed a constant number of times.
  5. 5. The condensation of a directed graph (one node per SCC) always has what property?

    A cycle among components would make their vertices mutually reachable, so those components would have been one SCC.

Summary

  • An SCC is a maximal set of vertices that all reach each other; every vertex is in exactly one.
  • Kosaraju: DFS to get finishing order, transpose the graph, DFS in decreasing finishing order. Components come out in topological order.
  • Tarjan: one DFS with disc, low and a stack; pop a component when low[v] == disc[v]. Components come out in reverse topological order.
  • Both run in O(V + E). Use an explicit stack for deep graphs.
  • Collapsing SCCs gives the condensation DAG; strongly connecting a graph needs max(sources, sinks) new edges.
  • Related: Bridges and Articulation Points use the same low-link idea on undirected graphs.

Next: Bridges and Articulation Points