Strongly Connected Components Theory

Problem

Partition a directed graph into maximal subsets where each pair of vertices is mutually reachable. Collapse each SCC to produce a condensation DAG enabling higher-level analyses (e.g., layering, DP across components).

Kosaraju's Two-Pass Method

• First DFS: push vertices by finish time (postorder).
• Transpose graph (reverse all edges).
• Second DFS in reverse finish order; each DFS tree = one SCC.
• Correctness hinges on finish-time ordering exposing source components first in GT.

Tarjan's Lowlink Method

• Single DFS assigns index (discovery time) and lowlink.
• lowlink[v] = smallest index reachable from v (following tree + back edges).
• When lowlink[v] == index[v], v is root of an SCC; pop stack until v.
• Stack membership distinguishes back edges from cross/forward edges.

Pseudocode (Kosaraju)

1KOSARAJU(G=(V,E)):
2  visited = { }
3  order = []
4  // 1st DFS: record finish order
5  for v in V:
6    if v not visited:
7      DFS1(v)
8  // transpose graph
9  GT = transpose(G)
10  visited = { }
11  components = []
12  // 2nd DFS on GT in reverse finish order
13  for v in reverse(order):
14    if v not visited:
15      C = []
16      DFS2(v, C)
17      components.push(C)
18  return components
19 
20DFS1(u):
21  visited.add(u)
22  for each (u->v) in Adj[u]:
23    if v not visited:
24      DFS1(v)
25  order.push(u)
26 
27DFS2(u, C):
28  visited.add(u); C.push(u)
29  for each (u->v) in AdjT[u]:
30    if v not visited:
31      DFS2(v, C)

Pseudocode (Tarjan)

1TARJAN(G):
2  index = 0
3  stack = []
4  onStack = {}
5  indices[v] = -1 for v
6  low[v] = 0
7  components = []
8  for v in V:
9    if indices[v] == -1:
10      STRONGCONNECT(v)
11  return components
12 
13STRONGCONNECT(v):
14  indices[v] = index; low[v] = index; index++
15  stack.push(v); onStack.add(v)
16  for (v->w) in Adj[v]:
17    if indices[w] == -1:
18      STRONGCONNECT(w)
19      low[v] = min(low[v], low[w])
20    else if w in onStack:
21      low[v] = min(low[v], indices[w])
22  if low[v] == indices[v]:
23    // root of SCC
24    component = []
25    repeat:
26      w = stack.pop(); onStack.remove(w)
27      component.push(w)
28    until w == v
29    components.push(component)

Lowlink Intuition

• Tracks earliest ancestor reachable via at most one back edge + tree edges.
• Root of SCC has lowlink == its own discovery index — no path to earlier active vertex.
• Back edges update lowlink allowing collapse detection.

Complexity

All edges/vertices processed constant times; Tarjan avoids explicit transpose pass.

Edge Cases

• Singleton vertex with no edges forms its own SCC.
• Self-loop vertex is an SCC of size 1 (loop does not enlarge component).
• Multiple identical edges do not affect partition.