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

---

The scenario matrix

Before we compute anything, let us list every class of input an SCC problem can be. Each worked example below is tagged with the cell it covers.

#	Case class	What makes it tricky	Example
A	One big cycle (whole graph = 1 SCC)	Everything merges; root only at the very end	Ex 1
B	Chain / DAG (no cycles)	Every node is its own SCC — degenerate	Ex 2
C	Two cycles joined by a one-way bridge	Bridge must NOT merge them	Ex 3
D	Single node, self-loop, no edges	Smallest / empty degenerate inputs	Ex 4
E	Cross edge into a finished SCC	The onStack trap in Tarjan	Ex 5
F	Multiple source SCCs (disconnected starts)	DFS must restart; order matters	Ex 6
G	Real-world word problem (currency / roads)	Model it as a graph first	Ex 7
H	Exam twist: condensation + count edges	Combine SCC with Topological Sort	Ex 8

We will do both Kosaraju and Tarjan where it teaches something, and lean on whichever is clearer otherwise.

---

---

Case A — the whole graph is one SCC

Tarjan, step by step (start DFS at 1):

1. Visit 1: disc[1]=low[1]=0, push 1. Why? First touch → discovery index is the current counter, and low starts equal to disc.
2. Follow $1\to 2$: disc[2]=low[2]=1, push 2. Then $2\to 3$: disc[3]=low[3]=2. Then $3\to 4$: disc[4]=low[4]=3. Why? Each is unvisited, so it becomes a tree edge; recurse deeper.
3. At 4, edge $4\to 1$. Node 1 is visited and on stack, so use disc[1]: low[4]=min(3,0)=0. Why disc not low? Rule: a back/stack edge lets us use only that one edge — take the discovery index of the target.
4. Return chain: low[3]=min(2,low[4])=0, low[2]=min(1,0)=0, low[1]=min(0,0)=0. Why? Tree edges propagate the child's low upward.
5. Root test at each node on return: only at 1 is low[1]==disc[1] ($0==0$). Pop everything down to 1 → SCC $\{1,2,3,4\}$. Why only at 1? Nodes 2,3,4 all had low < disc, meaning they can climb higher, so they are not roots.

Verify: Can we get $1⇝4$? $1\to 2\to 3\to 4$. ✓ And $4⇝1$? $4\to 1$. ✓ Every pair is mutually reachable → exactly 1 SCC. ✓

---

Case B — a pure DAG, every node alone

Tarjan:

1. disc[1]=low[1]=0, push 1. Tree edge $1\to 2$: disc[2]=low[2]=1. Tree edge $2\to 3$: disc[3]=low[3]=2.
2. At 3: no outgoing edges. low[3]==disc[3] ($2==2$) → root, pop $\{3\}$. Why? 3 cannot reach anyone older; it stands alone.
3. Back at 2: after recursion low[2]=min(1,low[3]). But 3 was already popped — the min uses low[3]=2, giving low[2]=min(1,2)=1. Still low[2]==disc[2] → root, pop $\{2\}$. Why does popping not corrupt this? For a tree edge we do use low[v], but since $v$ formed its own SCC, its low is $\ge disc[2]$ anyway, so 2 is unaffected.
4. Back at 1: edge $1\to 3$ — but 3 is not on stack (finished). So we skip it (neither tree nor stack edge). low[1]=min(0,low[2])=0 → root, pop $\{1\}$.

Verify: 3 separate SCCs, each a single node. Sanity: in a DAG no two nodes are mutually reachable (a cycle would be required), so #SCC = #vertices = 3. ✓

---

Case C — two cycles, one-way bridge

Kosaraju (to practise finish times):

1. DFS1 from 1: $1\to 2\to 3\to 4\to 5$. From 5, $5\to 4$ (visited), backtrack. Finish order (push on return): 5, 4, 3, 2, 1. So order=[5,4,3,2,1]. Why push on return? A node finishes only after all its descendants do.
2. Reverse: $2\to 1,3\to 2,1\to 3,4\to 3,5\to 4,4\to 5$. Why reverse? The sink of the reversed graph is the source of the original — the DFS tree there can't leak out.
3. DFS2 in decreasing finish order = [1,2,3,4,5]:
   • Start 1. In $G^{rev}$: $1\to 3\to 2\to 1$. Tree $\{1,2,3\}$ = SCC. Edge $4\to 3$ points into this group, but we traverse outgoing edges of the reversed graph, so we never reach 4.
   • Next unvisited 4 → $4\to 5\to 4$. Tree $\{4,5\}$ = SCC.

Verify: Is there a path $B⇝A$? From 4 or 5 you can only go $4\leftrightarrow 5$ — no edge leaves $B$. So no $4⇝1$; they are not merged. Two SCCs. In the condensation, $A\to B$ (from the bridge), so $A$ is the source, $B$ the sink. ✓

---

Case D — the tiniest / emptiest inputs

1. (a) DFS visits x, no edges. low[x]==disc[x] → root, pop $\{x\}$. 1 SCC. Why? A lone node is trivially mutually reachable with itself (empty path).
2. (b) Visit y, edge $y\to y$: y is on stack, so low[y]=min(disc[y],disc[y])=disc[y]. Root fires → $\{y\}$. 1 SCC (the self-loop does NOT create a second node). Why? A self-loop is a cycle of length 1 — but it's still just one vertex, one SCC.
3. (c) $p\to q$ only. disc[p]=0, tree edge to q disc[q]=1. At q: no edges, root → $\{q\}$. q popped. Back at p: low[p]=min(0,low[q])=0 → root → $\{p\}$. 2 SCCs. Why not 1? No path $q⇝p$; mutual reachability fails.

Verify: counts are (a) 1, (b) 1, (c) 2. Sanity: SCC count is always between 1 and $V$; here $V=1,1,2$ and we got $1,1,2$ — all in range. ✓

---

Case E — cross edge into a finished SCC (the onStack trap)

Correct Tarjan (start 3):

1. disc[3]=low[3]=0, push 3. Edge $3\to 1$: unvisited → tree edge. disc[1]=low[1]=1, push 1.
2. Edge $1\to 2$: disc[2]=low[2]=2, push 2. Edge $2\to 1$: 1 on stack → low[2]=min(2,disc[1])=1.
3. Return to 1: low[1]=min(1,low[2])=1. Root test: low[1]==disc[1] ($1==1$) → pop $\{2,1\}$ = SCC. Now 1 and 2 are off the stack. Why here? $\{1,2\}$ is a sink SCC; it finishes fully before we return to 3.
4. Back at 3: edge $3\to 4$: unvisited → disc[4]=low[4]=3, push 4. Edge $4\to 3$: 3 on stack → low[4]=min(3,disc[3])=0.
5. Return to 3: low[3]=min(0,low[4])=0. Root test 0==0 → pop $\{4,3\}$ = SCC.

Verify (why the trap merges wrongly): the cross edge $3\to 1$ was correctly ignored because by the time we finished exploring it, 1 was NOT on the stack. If instead you had run low[3]=min(low[3],low[1]) for it, you'd get low[3]=min(0,1)=0 — no change this time, but the real danger is doing low[3]=min(disc[3], disc[1]) without the onStack guard before 1 finished, dragging a finished SCC into the current one. Correct result: 2 SCCs $\{1,2\}$ and $\{3,4\}$. Both cycles are separate — there is no path $1⇝3$ (edges from $\{1,2\}$ never leave). ✓

---

Case F — multiple source SCCs, DFS must restart

Kosaraju:

1. DFS1 from 1: $1\to 2\to 3\to 4$ ($4\to 3$ visited, back). Finish: 4,3,2,1. Then outer loop hits 5 (unvisited): $5\to 6$. Finish 6,5. So order=[4,3,2,1,6,5], reversed decreasing = [5,6,1,2,3,4]. Why restart at 5? Node 5 was unreachable from 1 — the outer for loop guarantees we don't miss disconnected pieces.
2. Reverse: $2\to 1,1\to 2,4\to 3,3\to 4,3\to 2,6\to 5$.
3. DFS2 in [5,6,1,2,3,4]:
   • Start 5: $5\to ?$ nothing in $G^{rev}$ (edge is $6\to 5$, so 5 has no outgoing). Tree $\{5\}$ = SCC.
   • Next unvisited 6: $6\to 5$ (5 visited). Tree $\{6\}$ = SCC.
   • Next 1: $1\to 2\to 1$. Tree $\{1,2\}$. Edge $3\to 2$ points into this group in $G^{rev}$? It's $3\to 2$; from 2 we do NOT traverse it backward. Tree $\{1,2\}$ = SCC.
   • Next 3: $3\to 4\to 3$, and $3\to 2$ (2 visited). Tree $\{3,4\}$ = SCC.

Verify: SCCs $=\{1,2\},\{3,4\},\{5\},\{6\}$ → 4 SCCs. The outer DFS1 loop started fresh trees 2 times (at 1 and at 5). Sanity: 6 vertices, 4 SCCs, and the two chains 5→6 have no return edge so they split. ✓

---

Case G — a real-world word problem

1. Model: warehouses = vertices, routes = directed edges. "Round-trip cluster" = SCC. Why SCC? "Leave and always return" is exactly mutual reachability.
2. Tarjan from A: $A\to B\to C$, then $C\to A$ (A on stack) → low collapses to disc[A]. Root at A → $\{A,B,C\}$.
3. Continue $C\to D$: $D\to E$, $E\to D$ (D on stack) → root at D → $\{D,E\}$.
4. $E\to F$: F has no outgoing edge → root at F → $\{F\}$.

Verify: clusters $\{A,B,C\}$ and $\{D,E\}$ are round-trip; F is alone (no route back from F). Sanity: total vertices 6 = $3+2+1$. ✓

---

Case H — exam twist: condensation edge count

Let $X=\{A,B,C\}$, $Y=\{D,E\}$, $Z=\{F\}$.

1. Super-nodes: one per SCC → 3 ($X,Y,Z$).
2. Super-edges: scan every original edge; keep it only if it crosses between different SCCs (drop duplicates).
   • $C\to D$: $X\to Y$. ✓
   • $E\to F$: $Y\to Z$. ✓
   • All others ($A\to B$, $B\to C$, $C\to A$, $D\to E$, $E\to D$) stay inside an SCC → dropped. Why drop internal edges? Inside an SCC everything is one super-node; internal edges become self-loops, which a condensation omits. → 2 super-edges: $X\to Y\to Z$.
3. Topological order: since $X\to Y\to Z$ is already a chain (a DAG), the order is $X,Y,Z$. Why is it a DAG? The condensation of any directed graph is always acyclic (a cycle would merge those SCCs).

Verify: 3 super-nodes, 2 super-edges, topo order $X,Y,Z$. Sanity: a chain of 3 nodes has exactly $3-1=2$ edges and a unique topo order. ✓

---

Recall Rapid self-test (cover the answers)

Ex1 — SCC count of a 4-cycle? ::: 1 Ex2 — SCC count of a 3-node pure DAG? ::: 3 Ex4b — SCCs of a single self-loop node? ::: 1 Ex5 — do two cycles joined by a one-way cross edge merge? ::: No — 2 SCCs Ex6 — SCC count of the 6-node graph? ::: 4 Ex7 — is F in a round-trip cluster? ::: No, F is a singleton Ex8 — super-edges in the condensation? ::: 2

Back to the parent topic. Related drills: 2-SAT, Bridges and Articulation Points, Union-Find.