vault

Strongly Connected Components

20 min read

Strongly Connected Components

A strongly connected component (SCC) of a directed graph is a maximal subset of vertices S ⊆ V such that for every ordered pair (u, v) with u, v ∈ S, there is a directed path from u to v and a directed path from v to u. Every directed graph partitions uniquely into SCCs, and contracting each SCC to a single node yields the condensation G^SCC, which is always a directed acyclic graph (DAG). Two classical algorithms compute all SCCs in O(V + E) time: Tarjan’s algorithm (Tarjan, 1972) does it in a single DFS using discovery times and “lowlink” values, and Kosaraju’s algorithm (Sharir/Kosaraju, 1981) does it in two DFS passes — one on G, one on the transpose G^T. SCC decomposition is the foundation of 2-SAT, deadlock detection, dataflow analysis, web graph link analysis, and any reachability problem on directed graphs.

1. Intuition — Group Chats Where Every Message Travels Both Ways

Imagine a directed network of one-way roads connecting cities. A strongly connected cluster is a set of cities where, no matter which two you pick, you can drive from the first to the second and drive back — possibly via a different route. Within a cluster everyone is mutually reachable; between clusters the travel is one-way only.

Concretely: suppose A → B → C → A is a directed cycle. From A you can reach B (directly), C (via B), and back to A (via C). From C you can reach A (directly) and then everywhere else. The three cities form a single SCC. If we add D → A but no edge from anything in {A,B,C} back to D, then D is its own SCC — D can reach the {A,B,C} cluster but can’t be reached from it.

A useful mental model: take the graph, contract each cycle-laden cluster into a single super-node, and what remains is a DAG of clusters. That contracted DAG is the condensation graph, written G^SCC. SCCs are the strongly-connected building blocks; the condensation is the macroscopic skeleton showing how those blocks are arranged.

The reason both major algorithms work in linear time is that DFS already explores cycles: a directed cycle becomes a back edge in DFS (an edge from a descendant to an ancestor in the DFS tree, see Depth-First Search §6). Both Tarjan and Kosaraju leverage this — they just exploit the back-edge structure differently.

2. Tiny Worked Example

Vertices 0..7. Directed edges:

0 → 1, 1 → 2, 2 → 0,            (cycle 0-1-2 → SCC #1)
3 → 1, 3 → 4,                   (3 reaches SCC #1 but not vice-versa)
4 → 5, 5 → 6, 6 → 4,            (cycle 4-5-6 → SCC #2)
7 → 6                            (7 alone)

Visually:

         3 ──→ 4 ──→ 5
         │     ↑     │
         ↓     │     ↓
    0 ──→ 1 → 2     6
    ↑─────┘    │     │
              ↓     ↓
              0    SCC #2
                    ↑
                    7

(Arrow direction matters; the picture is approximate.)

SCCs:

  • {0, 1, 2} — closed cycle 0→1→2→0.
  • {4, 5, 6} — closed cycle 4→5→6→4.
  • {3} — singleton (no incoming edge from {0,1,2}, even though 3 reaches them).
  • {7} — singleton.

Condensation G^SCC: four super-nodes [0,1,2], [3], [4,5,6], [7]. Directed edges in the condensation: [3] → [0,1,2] (from 3→1), [3] → [4,5,6] (from 3→4), [7] → [4,5,6] (from 7→6). No cycles among super-nodes — the condensation is always a DAG (proved below in §6).

We will trace Tarjan’s algorithm on this graph in §3.3 and Kosaraju’s in §4.3.

3. Tarjan’s Algorithm — Single DFS with Lowlink

3.1 The Two Numbers per Vertex

Tarjan (1972) maintains, during a single DFS:

  • disc[u] — the discovery time of u: a counter incremented every time DFS first enters a vertex. The order is “1st vertex visited, 2nd vertex visited, …”.
  • low[u] — the lowlink of u: the smallest disc value reachable from u by following zero or more tree edges followed by at most one back edge (some textbooks include cross edges to other SCCs that happen to still be on the stack — see §3.4 for the precise definition Tarjan uses).

A vertex u is the root of its SCC’s subtree in the DFS forest iff low[u] == disc[u]. When DFS finishes such a root, every vertex of its SCC is sitting contiguously on top of an auxiliary stack that the algorithm maintains; popping until we re-pop u yields the SCC.

3.2 The Algorithm in Pseudocode

tarjan(G):
    counter := 0
    stack   := empty
    on_stack := set
    disc := array, all -1
    low  := array, all -1
    sccs := empty list of lists
    for each u in V:
        if disc[u] == -1:
            strongconnect(u)
    return sccs

strongconnect(u):
    disc[u] := counter
    low[u]  := counter
    counter := counter + 1
    push u on stack; on_stack[u] := true
    for each (u, v) in E:
        if disc[v] == -1:
            strongconnect(v)
            low[u] := min(low[u], low[v])           # back-propagate child's lowlink
        else if on_stack[v]:
            low[u] := min(low[u], disc[v])          # back/cross edge to current SCC stack
        # else: v is in a finished SCC; ignore
    if low[u] == disc[u]:                            # u is an SCC root
        component := empty list
        repeat:
            w := pop stack; on_stack[w] := false
            append w to component
        until w == u
        append component to sccs

3.3 Trace on the §2 Example

Start DFS at 0 (everything is undiscovered). Counter starts at 0.

StepActiondisclowStackNotes
1enter 00:00:0[0]
2enter 11:11:1[0,1]edge 0→1 is tree edge
3enter 22:22:2[0,1,2]edge 1→2 is tree edge
4examine 2→00:02:0[0,1,2]0 is on stack ⇒ back edge; low[2] = min(2, disc[0]=0) = 0
5finish 2low[2]=0 ≠ disc[2]=2 — not a root, leave on stack
6back-propagate to 11:0[0,1,2]low[1] = min(1, low[2]=0) = 0
7finish 1low[1]=0 ≠ disc[1]=1 — not root
8back-propagate to 00:0[0,1,2]low[0] = min(0, low[1]=0) = 0
9finish 0low[0]=0 == disc[0]=0 — root! Pop until 0 → SCC = {2, 1, 0}

Now DFS starts a fresh tree at 3 (next undiscovered). Eventually, when DFS finishes 4 (after visiting 5 and 6 and the back edge 6→4), we’ll find low[4] == disc[4], popping {6, 5, 4} as the second SCC. 3 ends up as a singleton SCC, and 7 likewise.

The crucial invariant: the auxiliary stack always contains, in DFS-discovery order, the vertices of all SCCs whose roots haven’t yet finished. The “pop until we re-pop the root” rule extracts exactly one SCC at a time.

3.4 Why low[u] = min(low[u], disc[v]) for Back/Cross Edges, Not low[v]

Subtle but critical: when DFS examines edge (u, v) and v has already been discovered, we update low[u] using disc[v], not low[v]. The reason: low[v] may have been updated by a finished sibling subtree’s edges that aren’t actually reachable from u. Using disc[v] is the safe, sound choice that makes the proof go through. (This is the classic gotcha; many erroneous implementations use low[v] and produce wrong SCCs on graphs with cross edges. See §11.1.)

3.5 Python Implementation (Iterative — Avoids Recursion Limit)

def tarjan_scc(graph: dict[int, list[int]], n: int) -> list[list[int]]:
    """
    graph: adjacency list, vertex -> list of out-neighbors.
    n: number of vertices, labeled 0..n-1.
    Returns: list of SCCs, each as a list of vertices.
    """
    disc = [-1] * n
    low  = [-1] * n
    on_stack = [False] * n
    stack = []                  # auxiliary stack of vertices in active SCC search
    sccs = []
    counter = [0]               # mutable wrapper for closure assignment
 
    def strongconnect(start: int) -> None:
        # Iterative DFS using an explicit work stack of (vertex, neighbor-iterator)
        work = [(start, iter(graph.get(start, [])))]
        disc[start] = low[start] = counter[0]; counter[0] += 1
        stack.append(start); on_stack[start] = True
 
        while work:
            u, it = work[-1]
            try:
                v = next(it)
                if disc[v] == -1:
                    disc[v] = low[v] = counter[0]; counter[0] += 1
                    stack.append(v); on_stack[v] = True
                    work.append((v, iter(graph.get(v, []))))
                elif on_stack[v]:
                    low[u] = min(low[u], disc[v])     # back/cross edge inside active SCC
                # else: v in finished SCC; ignore
            except StopIteration:
                work.pop()
                if work:
                    parent = work[-1][0]
                    low[parent] = min(low[parent], low[u])
                if low[u] == disc[u]:                  # SCC root
                    component = []
                    while True:
                        w = stack.pop(); on_stack[w] = False
                        component.append(w)
                        if w == u: break
                    sccs.append(component)
 
    for u in range(n):
        if disc[u] == -1:
            strongconnect(u)
    return sccs

Iterative form is preferable in Python: a graph with a long chain (e.g., 10^5 vertices) overflows the default recursion limit of 1000 (see Depth-First Search §15.1).

3.6 Complexity

  • Time: O(V + E). Each vertex is pushed/popped at most once on each of the two stacks; each edge is examined exactly once.
  • Space: O(V) for disc, low, on_stack, the auxiliary stack, and the work stack.

The O(V + E) is tight: you must read every edge to know whether it’s a back edge.

4. Kosaraju’s Algorithm — Two DFS Passes

4.1 The Idea

The transpose graph G^T has the same vertices as G but every edge reversed. Crucial fact: G and G^T have exactly the same SCCs — strong connectivity is symmetric in edge direction.

Kosaraju exploits this with three steps:

  1. Run DFS on G, recording the finish order of vertices (post-order). Push each vertex onto a stack as DFS finishes it.
  2. Build G^T (reverse every edge).
  3. Run DFS on G^T, picking the next unvisited vertex from the top of the finish-order stack. Each DFS tree in this second pass is exactly one SCC.

4.2 Pseudocode

kosaraju(G):
    visited := set
    order   := empty list                            # finish order (oldest at front)
    for each u in V:
        if u not in visited:
            dfs1(u)

    G_T := transpose(G)
    visited := empty set
    sccs := empty list
    for u in reversed(order):                        # latest-finished first
        if u not in visited:
            component := empty list
            dfs2(u)                                  # collect all reachable in G_T
            append component to sccs
    return sccs

dfs1(u):                                              # post-order push
    visited.add(u)
    for each v in G[u]:
        if v not in visited: dfs1(v)
    order.append(u)

dfs2(u):
    visited.add(u); component.append(u)
    for each v in G_T[u]:
        if v not in visited: dfs2(v)

4.3 Trace on the §2 Example

Pass 1 (DFS on G). Suppose we start at 0. The DFS visits 0 → 1 → 2 → (back edge to 0; nothing) → finish 2 → finish 1 → finish 0. Then 3 (next unvisited): 3 → 4 → 5 → 6 → (back edge to 4; nothing) → finish 6 → finish 5 → finish 4 → finish 3. Finally 7: 7 → (6 visited) → finish 7.

Finish-order stack (oldest at bottom): [2, 1, 0, 6, 5, 4, 3, 7]. Reversed: process in order 7, 3, 4, 5, 6, 0, 1, 2.

Pass 2 (DFS on G^T). G^T reverses every edge. Edges in G^T: 1→0, 2→1, 0→2, 1→3, 4→3, 5→4, 6→5, 4→6, 6→7.

  • Start at 7 (top of stack). DFS in G^T: 7 has no out-edges in G^T (7→6 reverses to 6→7, which is incoming to 7). SCC = {7}.
  • Next unvisited: 3. DFS in G^T from 3: 3 has no out-edges in G^T (since 3 had only out-edges originally, which become incoming in G^T). SCC = {3}.
  • Next: 4. From 4 in G^T: 4 → 3 (3 visited; skip) and 4 → 6 → 5 → 4 (cycle). SCC = {4, 6, 5}.
  • Next: 0. From 0 in G^T: 0 → 2 → 1 → 0. SCC = {0, 2, 1}.

Same SCCs as Tarjan, in different order.

4.4 Python Implementation

def kosaraju_scc(graph: dict[int, list[int]], n: int) -> list[list[int]]:
    visited = [False] * n
    order = []                                       # finish-order
 
    def dfs1(start: int) -> None:
        stack = [(start, iter(graph.get(start, [])))]
        visited[start] = True
        while stack:
            u, it = stack[-1]
            for v in it:
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, iter(graph.get(v, []))))
                    break
            else:
                order.append(u)
                stack.pop()
 
    for u in range(n):
        if not visited[u]:
            dfs1(u)
 
    # Build transpose
    g_t: dict[int, list[int]] = {u: [] for u in range(n)}
    for u, neighbors in graph.items():
        for v in neighbors:
            g_t[v].append(u)
 
    visited = [False] * n
    sccs = []
    for u in reversed(order):
        if not visited[u]:
            component = []
            stk = [u]; visited[u] = True
            while stk:
                w = stk.pop(); component.append(w)
                for v in g_t[w]:
                    if not visited[v]:
                        visited[v] = True
                        stk.append(v)
            sccs.append(component)
    return sccs

4.5 Why It Works (Proof Sketch)

Pick the vertex u with the latest finish time in pass 1. We claim DFS from u in G^T reaches exactly the SCC containing u.

  • Every vertex v in u’s SCC is reachable from u in G (definition of SCC) and reachable from u in G^T too (since SCCs are direction-symmetric). So pass 2 from u visits all of u’s SCC.
  • Suppose pass 2 from u also reaches some w not in u’s SCC. Then there’s a path u ⇝ w in G^T, i.e., w ⇝ u in G. So w’s SCC has a path to u’s SCC in the condensation. A theorem about DFS finish times (CLRS Lemma 22.14) says: if there is an edge in G^SCC from SCC C to SCC C', then the latest finish time in C is later than the latest finish time in C'. Combined with our choice of u (latest overall finish), no SCC has an edge to u’s SCC, contradiction.

Thus pass 2 from u recovers exactly u’s SCC. After marking those vertices visited, the next unvisited vertex with the next-latest finish time triggers the same argument inductively.

4.6 Complexity

  • Time: O(V + E) — three linear-time passes (two DFS, one transpose construction).
  • Space: O(V + E) — explicit transpose graph adds an extra adjacency list of size E.

Kosaraju’s O(V + E) time is the same as Tarjan’s, but its constant factor is roughly 2× Tarjan’s (two DFS passes plus building G^T). In practice Tarjan is preferred when speed matters; Kosaraju is preferred when clarity matters (the algorithm is much easier to explain on a whiteboard).

5. Tarjan vs Kosaraju — Practical Differences

PropertyTarjanKosaraju
DFS passes12
Auxiliary structuresdisc, low, on_stack, work stackfinish-order list, transpose graph
Needs G^T explicitly?NoYes
Constant factor~1×~2×
Code complexityHigher (subtle low update rules)Lower (just two DFS)
Easy to parallelize?NoMarginally — pass 2 components are independent
Easier to prove correct on a whiteboard?NoYes
Output orderingSCCs in reverse-topological order of condensationSCCs in topological order of condensation

Tarjan’s bonus property: the SCCs are output in reverse topological order of the condensation (sinks first). This is convenient for some downstream algorithms (e.g., 2-SAT propagates assignments in this order).

6. The Condensation Graph and Why It’s a DAG

Define G^SCC (the condensation) by contracting each SCC to a single super-node, keeping an edge (C, C') between super-nodes whenever G had any edge from a vertex in C to a vertex in C'.

Theorem. G^SCC is a DAG.

Proof. Suppose for contradiction there’s a cycle C_1 → C_2 → ... → C_k → C_1 in G^SCC. Then there’s a vertex u_i ∈ C_i and v_i ∈ C_{i+1} with edge (u_i, v_i) in G. Within each SCC there’s a path from v_i back to u_{i+1}. Stitching these together gives a cycle through all of C_1 ∪ ... ∪ C_k, meaning all those vertices are mutually reachable — they should have been one SCC, not k. Contradiction.

The condensation is the right abstraction for many directed-graph problems. After computing SCCs, replace G by G^SCC and run a DAG algorithm (topological sort, DAG shortest path, DAG DP). See Topological Sort for DAG-specific algorithms.

7. Use Cases

7.1 2-Satisfiability (2-SAT)

Given a Boolean formula in conjunctive normal form where every clause has exactly two literals (e.g., (x_1 ∨ ¬x_2) ∧ (x_3 ∨ x_1) ∧ ...), is it satisfiable?

Encode each clause (a ∨ b) as two implications: ¬a ⇒ b and ¬b ⇒ a. Build the implication graph with 2n vertices (one per literal x_i and ¬x_i) and these directed edges. Compute SCCs.

Theorem (Aspvall, Plass, Tarjan 1979). The formula is satisfiable iff no variable x_i appears in the same SCC as its negation ¬x_i. Furthermore, a satisfying assignment can be extracted in O(V + E) by processing SCCs in reverse topological order: assign x_i = true if x_i’s SCC is finished after ¬x_i’s SCC. Tarjan’s algorithm gives this order for free, which is why it’s the algorithm of choice for 2-SAT.

7.2 Deadlock Detection in Operating Systems

Build the resource-allocation graph: vertices are processes and resources; edge P → R means process P is waiting for resource R; edge R → P means R is held by P. A deadlock corresponds to a cycle, which (in this graph’s structure) corresponds to an SCC containing at least one cycle. SCC decomposition identifies all deadlock candidates in O(V + E).

7.3 Dataflow and Compiler Optimization

The call graph of a program (vertices = functions, edges = “calls”) has SCCs corresponding to mutually-recursive function groups. Optimizations like inlining and interprocedural analysis are typically applied per SCC in reverse topological order (sinks first), so analyzing an SCC has up-to-date info about its callees. Same idea for the dependence graph in instruction scheduling.

7.4 Web Graph and PageRank

The web graph (pages linking to pages) decomposes into a giant central SCC (the “core” — pages mutually reachable via hyperlinks), tendrils leading into it, tendrils leading out, and disconnected islands. This bowtie structure (Broder et al., 2000) is empirically the shape of the web. PageRank on the core SCC differs algebraically from PageRank including dangling sinks; SCC analysis is the preprocessing step.

7.5 Cycle Detection that Returns the Cycle

A standalone cycle check returns true/false. SCC decomposition returns the actual cycle structure: any SCC of size ≥ 2, or any singleton SCC with a self-loop, contains a cycle. Useful when the problem needs the cycle itself, not just its existence.

7.6 Reducing Problems on Directed Graphs to Problems on DAGs

Many graph problems are easy on DAGs and hard on general directed graphs. SCC decomposition + replacing G by G^SCC is a generic reduction. Examples: longest path (NP-hard on general graphs, O(V+E) on DAGs); counting paths (DP on DAGs); coloring (any DAG is k-colorable for k ≤ longest_chain + 1).

8. Variants Worth Knowing

8.1 Gabow’s Algorithm

Gabow (2000) gives another single-pass algorithm using two stacks and only the discovery times (no low array). Functionally equivalent to Tarjan with the same O(V+E) bound; some prefer it because the proof and stack manipulation are easier to follow. Same asymptotic; different constants.

8.2 Path-Based Algorithms

A family of single-pass algorithms (Cheriyan-Mehlhorn, Gabow) all do “single DFS, two stacks, output SCCs upon completing roots.” They differ in bookkeeping, not asymptotic behavior.

8.3 Online and Incremental SCC

If edges are added one at a time and you want to maintain SCCs, specialized algorithms (Haeupler-Kavitha-Mathew-Sen-Tarjan, 2012) achieve O(E^{1+1/k}) total update time. Edge deletion is much harder; no good fully-dynamic SCC algorithm is known.

8.4 Parallel SCC

The DCSC (Divide and Conquer SCC, Fleischer-Hendrickson-Pinar 2000) algorithm parallelizes SCC computation by picking a pivot, computing forward and backward reachability, and recursing. O(V + E) total work but logarithmic-depth parallel recursion. Used in graph-processing frameworks like Pregel and GraphX.

9. Common Interview Problems

ProblemPattern
LC 1192 — Critical Connections in a NetworkBridges (related, not SCC); see Bridges and Articulation Points
Codeforces / classic — “2-SAT”Implication graph + Tarjan SCC
LC 2360 — Longest Cycle in a GraphFind SCC of size ≥ 2; report the longest
LC 2876 — Count Visited Nodes in a Directed GraphSCC + DP on condensation
Classic — “Mother vertex”Run DFS once, take the last-finishing vertex; verify with second DFS (a degenerate Kosaraju)
Classic — “Find all cycles in a directed graph”SCC + within-SCC enumeration
Compiler — “Mutually recursive function groups”Call-graph SCC decomposition
OS — “Detect deadlock in resource-allocation graph”SCC decomposition

If a problem mentions “strongly connected”, “mutually reachable”, “cycle structure of a directed graph”, “2-SAT”, or “condensation” — SCC is on the shortlist.

10. Diagram — Tarjan’s disc and low on a Small SCC

flowchart TD
  A((A<br/>disc=0<br/>low=0)) --> B((B<br/>disc=1<br/>low=0))
  B --> C((C<br/>disc=2<br/>low=0))
  C -.back edge.-> A
  D((D<br/>disc=3<br/>low=3)) --> A

What this diagram shows. Solid arrows are tree edges from the DFS spanning tree; the dashed arrow is a back edge (C → A, where A is C’s ancestor). Discovery times are assigned in DFS order: A=0, B=1, C=2, then D=3. The lowlink of C is updated by the back edge: low[C] = min(disc[C]=2, disc[A]=0) = 0. That value back-propagates: low[B] = min(1, low[C]=0) = 0, then low[A] = min(0, low[B]=0) = 0. When DFS finishes A, it sees low[A] == disc[A], identifying A as the root of an SCC; the auxiliary stack contains [A, B, C] which are popped together as one SCC. D, with no back edge to {A,B,C} or itself, has low[D] == disc[D] == 3, so D forms its own singleton SCC.

11. Pitfalls

11.1 Using low[v] Instead of disc[v] for Back/Cross Edges

The single most common bug. When (u, v) is a back/cross edge and v is on the stack, the update is low[u] = min(low[u], disc[v]). Using low[v] here can pull in lowlinks from sibling subtrees that aren’t truly reachable from u, merging SCCs that should stay separate. Symptoms: passes simple cycle tests, fails on graphs with cross-SCC structure.

11.2 Forgetting to Skip Edges to Finished SCCs

When (u, v) is examined and v is already discovered but not on the stack, v is in a finished SCC; do nothing. Updating low[u] from such a v is wrong. The on_stack array is what distinguishes “active SCC search” from “finished”.

11.3 Recursion Depth in Python

A long chain (e.g., 0 → 1 → ... → 10^5) blows the default recursion limit. Use iterative DFS (as in §3.5) or sys.setrecursionlimit(N) with a generous N. The iterative version is preferable for graphs of unknown shape.

11.4 Confusing Strongly Connected with (Weakly) Connected

A directed graph is weakly connected if its underlying undirected graph is connected — every vertex can reach every other when we forget edge direction. Strong connectivity demands directed paths in both directions. A tree-like directed graph (A → B → C) is weakly connected but has three SCCs, not one.

11.5 Empty Graphs and Singleton Vertices

A vertex with no edges (in or out) is its own SCC of size 1. Make sure your code initializes/iterates over every vertex, not just those with outgoing edges. Missing isolated vertices is a silent correctness bug.

11.6 Self-Loops

A vertex u with edge u → u is a singleton SCC of size 1, but it contains a cycle. When asked “does this SCC contain a cycle?” treat self-loops specially: SCC of size ≥ 2 always has a cycle; SCC of size 1 has a cycle iff it has a self-loop.

11.7 Modifying Adjacency List During DFS

Both Tarjan and Kosaraju iterate over graph[u]; mutating it during the iteration is undefined. Treat the input graph as read-only.

11.8 Off-By-One in Vertex Numbering

If your input is 1-indexed but your arrays are 0-indexed (or vice versa), you’ll get index errors or silent wrong answers (e.g., vertex 0 treated as never-discovered when it shouldn’t be). Normalize at the input boundary.

12. Common Interview Problems

(Combined with §9 above for completeness.)

13. Open Questions

  • Is there a fully dynamic SCC algorithm (supporting both insertions and deletions) with sub-O(V+E) per-update time? Open as of 2024 to my knowledge — verify against latest STOC/FOCS.
  • How does Tarjan’s algorithm behave on graphs that don’t fit in memory? External-memory variants exist (Sibeyn, Abello-Buchsbaum-Westbrook); not standard interview material.

14. See Also

Graph View

Backlinks