Strongly Connected Components (SCC) — Kosaraju's algorithm, Tarjan's algorithm

What exactly is an SCC?

Kosaraju's algorithm — two passes of DFS

WHY does this work? (derive it, don't memorize)

Key fact about finish times. Suppose SCCs $A$ and $B$ exist with an edge $A \to B$ in the condensation (so $A$ comes "before" $B$ ). Then: $\max_{u \in A} f(u) \;>\; \max_{v \in B} f(v)$ i.e. the SCC that is "earlier" in the DAG finishes later.

Proof sketch (Why this is true):

Case 1: DFS first enters $A$ . Since $A$ can reach $B$ , DFS will explore all of $A$ and $B$ before returning, so the first node touched in $A$ finishes after everything in $B$ . ✓
Case 2: DFS first enters $B$ . Because the condensation is a DAG and edge goes $A\to B$ , there is no path $B \to A$ . So $B$ 's DFS finishes entirely without touching $A$ . Later DFS starts in $A$ → $A$ finishes after $B$ . ✓

Now reverse the graph. In $G^{\text{rev}}$ , the edge becomes $B \to A$ . We start the second DFS from the vertex of highest finish time — that vertex lies in a "source" SCC of the original DAG (no SCC finishes later). In $G^{\text{rev}}$ that SCC is a sink: its edges to other SCCs are reversed and now point into it, so the DFS cannot escape to another SCC. Hence one DFS tree = exactly one SCC. Removing it, repeat. ∎

Formula Kosaraju — pseudocode

order = []                      # fill by finish time
for each unvisited u: DFS1(u)   # on G; on return push u to order

Grev = reverse(G)
reverse(order)                  # decreasing finish time
for each u in order:
    if unvisited: DFS2(u) on Grev  # one whole tree = one SCC

Complexity: two DFS + one reversal $= O(V+E)$ time, $O(V+E)$ space.

Worked example Trace on a tiny graph

Edges: $1\to2,\ 2\to3,\ 3\to1,\ 3\to4,\ 4\to5,\ 5\to4$ .

DFS1 from 1: explores 1→2→3→4→5, backtracks. Finish order (push on return): 5,4,3,2,1. So order = [5,4,3,2,1], reversed = [1,2,3,4,5]. Why push on return? A node is "finished" only after all descendants finish.
Reverse graph: $2\to1,3\to2,1\to3,4\to3,5\to4,4\to5$ .
DFS2 in order [1,2,3,4,5]:
- Start 1 → reaches 3,2 (in $G^{rev}$ , $1\to3\to2$ , $2\to1$ ). Tree $\{1,2,3\}$ = SCC. Why doesn't it grab 4? Edge $4\to3$ points into this group; we never traverse it backward.
- Next unvisited is 4 → reaches 5. Tree $\{4,5\}$ = SCC.
Answer: $\{1,2,3\},\{4,5\}$ . ✓

Tarjan's algorithm — one pass of DFS

WHY `low[u] == disc[u]` marks a root

We keep nodes of the current DFS path/SCC-candidates on an explicit stack, with an onStack[] flag.
low[u] says "the earliest-discovered node $u$ can loop back to without leaving the current SCC."
If $u$ can reach an earlier node ( $low[u] < disc[u]$ ), then $u$ isn't the entry of its SCC — some ancestor is.
If $u$ cannot climb above itself ( $low[u]==disc[u]$ ), $u$ is the highest node of its SCC = its root. Pop the stack down to $u$ ; those vertices are one SCC.

Formula Tarjan — update rules

Initialize a global counter. On visiting $u$ : disc[u]=low[u]=index++, push $u$ , onStack[u]=true. For each edge $u\to v$ : $\text{if } v \text{ unvisited: } \mathtt{dfs}(v);\ low[u]=\min(low[u],low[v])$ $\text{else if } onStack[v]:\ low[u]=\min(low[u],disc[v])$ After the loop, if low[u]==disc[u]: pop until $u$ inclusive → emit one SCC. Note the asymmetry: use $low[v]$ for tree edges (full subtree info), but only $disc[v]$ for back/cross edges (you may use just one such edge — using $low[v]$ would be wrong). Complexity: single DFS $= O(V+E)$ .

Common mistake Steel-manning the classic blunders

1. "Tarjan: use low[v] for back/cross edges too." Why it feels right: low always carries the "deepest reachable" info, so why not reuse it? The fix: low[v] may include a node that has already been popped off the stack (a different, finished SCC). Using disc[v] (only when onStack[v]) restricts you to the current component, which is the whole point. Using low[v] here can merge separate SCCs.

2. "Kosaraju: do second DFS in the SAME order as the first." Why it feels right: an order is an order. The fix: the theorem only holds for decreasing finish time on the reversed graph. Wrong order ⇒ a DFS tree can leak into another SCC.

3. "SCC = connected components, just on directed graphs." Why it feels right: the names sound similar. The fix: undirected connectivity only needs a path; SCC needs paths both ways. Two nodes with only $u\to v$ are in different SCCs.

4. "Forgetting onStack." Without it you'd treat a back-edge into an already-finished SCC as if it merged them.

Recall Feynman: explain to a 12-year-old

Imagine cities connected by one-way roads. A "club" is a group of cities where you can drive from any city to any other and come back — a round trip is always possible. That club is an SCC. Kosaraju explores every city twice: first to note the order people finish their tour, then it flips all the road directions and re-tours starting from whoever finished last — each new tour fences off exactly one club. Tarjan is the smart traveler who does it in one go: he keeps a stack of "cities I might still loop back to," and the moment he realizes a city can't reach anyone older than itself, he knows that city is the leader of a club and scoops everyone above it off the stack.

Flashcards

What is an SCC in a directed graph?

A maximal set of vertices where every pair is mutually reachable (paths both directions).

What is the condensation of a graph?

Contract each SCC to one node; the result is always a DAG.

Kosaraju's three steps?

(1) DFS on G recording finish times; (2) reverse the graph; (3) DFS on reversed graph in decreasing finish-time order — each tree is an SCC.

Why does the highest-finish-time vertex matter in Kosaraju?

It lies in a source SCC of the original DAG = a sink SCC in the reversed graph, so its DFS tree can't leak into other SCCs.

In Tarjan, what does low[u] mean?

The smallest discovery index reachable from u via tree edges plus at most one edge to a node still on the stack.

Tarjan condition for an SCC root?

low[u] == disc[u]; pop the stack down to and including u to form the SCC.

Tarjan: when to use low[v] vs disc[v]?

low[v] for tree edges (recursive child); disc[v] only when onStack[v] for back/cross edges.

Time complexity of both algorithms?

O(V+E).

Why is onStack[] needed in Tarjan?

To ignore edges into already-finished SCCs, so separate components don't get merged.

Difference between SCC and undirected connected component?

SCC needs mutual (two-way) reachability; undirected components only need a single path.

Connections

Depth First Search — both algorithms are DFS skeletons.
Topological Sort — the condensation DAG can be topologically ordered.
Directed Acyclic Graph (DAG) — what you get after contracting SCCs.
2-SAT — solved by SCCs on the implication graph.
Bridges and Articulation Points — Tarjan's low-value idea reused on undirected graphs.
Union-Find — alternative connectivity tool (undirected only).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, SCC ka matlab hai directed graph mein aise nodes ka group jahan har node se har doosre node tak ja sakte ho aur wapas bhi aa sakte ho. One-way roads waale shehron jaisa socho — agar ek club ke andar saare cities mein round-trip possible hai, toh wo ek SCC hai. SCC important kyun? Kyunki jab tum har SCC ko ek single node maan ke "shrink" karte ho, toh poora graph ek DAG ban jaata hai — saare cycles gaayab, aur DAG par kaam (topological order, longest path) bahut easy ho jaata hai.

Kosaraju ka funda simple hai: pehle normal DFS chalao aur har node ka finish time note karo (jab uske saare children khatam ho jaate hain). Phir saare edges ulta kar do (reverse graph), aur jis node ka finish time sabse zyada hai usse start karke DFS karo decreasing finish-time order mein. Har DFS tree exactly ek SCC dega. Yaad rakhna — ulta graph aur decreasing order, dono zaroori hain, warna answer galat aayega.

Tarjan smart hai — sirf ek DFS mein kaam ho jaata hai. Har node ko disc (discovery index) deta hai aur low track karta hai (sabse purana node jahan tak wapas pahunch sakte ho). Ek explicit stack rakhta hai with onStack flag. Jab kisi node par low[u] == disc[u] mile, samajh lo wo apne SCC ka leader hai — stack se us node tak sab pop kar do, wahi ek SCC hai. Important rule: tree edge ke liye low[v] lo, lekin back/cross edge ke liye sirf disc[v] (aur tabhi jab onStack[v] true ho) — warna alag SCCs galti se merge ho jaayenge.

Dono O(V+E) hain. Exam/interview mein: agar one-pass aur low-link concept chahiye toh Tarjan, agar simple "DFS + reverse" yaad rakhna easy lage toh Kosaraju. Donon ki backbone DFS hi hai.

Strongly Connected Components (SCC) — Kosaraju's algorithm, Tarjan's algorithm

What exactly is an SCC?

Kosaraju's algorithm — two passes of DFS

WHY does this work? (derive it, don't memorize)

Tarjan's algorithm — one pass of DFS

WHY `low[u] == disc[u]` marks a root

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections