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

An SCC needs a path both ways.

• (a) $1,2$ — same SCC. $1\to 2$ directly, and $2\to 3\to 1$ back. Round trip exists.
• (b) $1,4$ — different. You can go $1\to 2\to 3\to 4$ (forward), but there is no way back from $4$ to $1$: from $\{4,5\}$ every edge stays inside $\{4,5\}$.
• (c) $4,5$ — same SCC. $4\to 5$ and $5\to 4$ directly.
• (d) $2,5$ — different. Same reason as (b): $\{4,5\}$ has no exit edge back to $\{1,2,3\}$.

So the SCCs are $\{1,2,3\}$ and $\{4,5\}$. Same-SCC pairs: (a) and (c).

The condensation contracts each SCC to one node, so it has $3$ nodes: $\{a\},\{b,c\},\{d\}$. It has the $3$ listed edges. A DAG (Directed Acyclic Graph) is a directed graph with no cycle. Trace: from $\{a\}$ you can reach $\{b,c\}$ and $\{d\}$, but nothing loops back to $\{a\}$; $\{d\}$ has no outgoing edge. No cycle ⇒ yes, it is a DAG. (The condensation is always a DAG — if it had a cycle, those SCCs would be mutually reachable and would merge into one.)

Why push on return, not on entry? A vertex is "finished" only after all its descendants finish; pushing on return is what records that. Walk it:

• Enter $1$ → go to $2$ → go to $3$. From $3$ neighbours are $1$ (visited) and $4$; go to $4$ → go to $5$.
• From $5$ the only edge is $5\to 4$ (visited). $5$ finishes → push 5.
• Back at $4$: neighbour $5$ visited. $4$ finishes → push 4.
• Back at $3$: all neighbours done. $3$ finishes → push 3.
• Back at $2$, then $1$: finish → push 2, push 1.

Finish order (push sequence): $[5,4,3,2,1]$. Reversed (decreasing finish time): $[1,2,3,4,5]$. This reversed list is the exact order DFS2 will use.

Reversed edges: $2\to 1,3\to 2,1\to 3,4\to 3,5\to 4,4\to 5$. Process order $[1,2,3,4,5]$:

• Start 1 (unvisited). In $G^{\text{rev}}$: $1\to 3\to 2$, and $2\to 1$ (visited). The whole tree grown from $1$ is $\{1,2,3\}$ = one SCC. Why does the tree stop here? Edge $4\to 3$ points into this group, and DFS only follows arrows forward, so we can never step out to $4$.
• Next unvisited is 4: $4\to 5$ and $4\to 3$ (visited). Tree $=\{4,5\}$ = one SCC.

SCCs: $\{1,2,3\}$ and $\{4,5\}$. Why one tree = one SCC? Because DFS2 always starts in a sink SCC of $G^{\text{rev}}$ (proved in L5.1), which has no outgoing edges to unfinished components, so a single exploration captures exactly one component.

Process edges in the order they appear. Discovery order is $1,2,3,4,5$, so $disc=\{1:0,2:1,3:2,4:3,5:4\}$ and initially $low[u]=disc[u]$ for each. Stack grows $[1,2,3,4,5]$, all onStack = true.

Step through, deepest first (recursion returns bottom-up):

• At $5$: its only edge $5\to 4$. Is $4$ on the stack? Yes. So this is a back edge, use disc: $low[5]=\min (low[5],disc[4])=\min (4,3)=3$. Loop done. Check root: $low[5]=3\ne disc[5]=4$ ⇒ $5$ is not a root, do not pop. Return to $4$.
• At $4$ (after recursing into $5$): $5\to 4$ was a tree edge $4\to 5$, so use low: $low[4]=\min (low[4],low[5])=\min (3,3)=3$. Now check root: $low[4]=3=disc[4]$ ⇒ root at 4. Pop the stack down to $4$: pop $5$, pop $4$ ⇒ SCC $\{4,5\}$. Both get onStack=false. Return to $3$.
• At $3$ (after recursing into $4$): first the tree edge $3\to 4$ returns: $low[3]=\min (low[3],low[4])=\min (2,3)=2$. Then edge $3\to 1$: is $1$ on the stack? Yes ⇒ back edge, use disc: $low[3]=\min (2,disc[1])=\min (2,0)=0$. Loop done. Root check: $low[3]=0\ne disc[3]=2$ ⇒ not a root. Return to $2$.
• At $2$: tree edge $2\to 3$ returns: $low[2]=\min (low[2],low[3])=\min (1,0)=0$. Not a root ($0\ne 1$). Return to $1$.
• At $1$: tree edge $1\to 2$ returns: $low[1]=\min (low[1],low[2])=\min (0,0)=0$. Root check: $low[1]=0=disc[1]$ ⇒ root at 1. Pop down to $1$: pop $3$, pop $2$, pop $1$ ⇒ SCC $\{1,2,3\}$.

Why does $low[u]=disc[u]$ mark a root? It means $u$ cannot reach any vertex discovered earlier than itself (without leaving the current stack). So no ancestor is reachable back — $u$ is the highest (earliest-discovered) vertex of its SCC, i.e. its entry point. Everything sitting above $u$ on the stack was reached from $u$ and can loop back to it, so they form exactly one component.

Final: $disc=\{1:0,2:1,3:2,4:3,5:4\}$, $low=\{1:0,2:0,3:2,4:3,5:3\}$. SCCs: $\{1,2,3\}$, $\{4,5\}$ — same answer as Kosaraju, in one pass.

A tree edge means $v$ is a fresh child whose whole subtree we are about to explore; its final $low[v]$ summarises everything reachable below $u$, so we absorb it fully. A back/cross edge to an on-stack node is a single shortcut — Tarjan's rule says you may climb using at most one such edge. Using $disc[v]$ records exactly "I reached a vertex first discovered at time $disc[v]$." Using $low[v]$ would let $u$ inherit somewhere $v$ can reach through further edges, possibly a vertex in a finished, different SCC — wrongly merging two components.

Concrete minimal counterexample. Four vertices, edges: $1\to 2,2\to 1,2\to 3,3\to 4,4\to 3,4\to 1.$ True SCCs: $\{1,2\}$ and $\{3,4\}$ (each is a 2-cycle; $2\to 3$ is a one-way bridge, and $4\to 1$ is a cross edge back to the first component). Start at $1$: discovery $1,2,3,4$ with $disc=\{1:0,2:1,3:2,4:3\}$.

• Correct Tarjan: at $4$, edge $4\to 1$ — but by the time we test it, whether $1$ is on the stack decides everything. Under a start that finishes $\{1,2\}$-style ordering, $4\to 3$ (tree/back inside $\{3,4\}$) gives $low[4]=disc[3]=2=disc[3]$; $3$ becomes root ⇒ SCC $\{3,4\}$ correctly, provided $4\to 1$ is ignored because that path must not import component $\{1,2\}$.
• Buggy version uses $low[1]$ for the cross edge $4\to 1$: since $low[1]=0$, we would set $low[4]=0<disc[3]$, so $3$ never becomes a root and $\{3,4\}$ gets glued onto $\{1,2\}$ — one wrong giant SCC instead of two. That is the merge the disc+onStack rule prevents.

Let $f(x)$ be the finish time of vertex $x$.

• Case 1 — DFS enters $A$ before touching any of $B$. Since $A\to B$ exists and $A$ is strongly connected, DFS from the first $A$-vertex reaches all of $A$ and then all of $B$ before it can return. So that first $A$-vertex finishes after everything in $B$ ⇒ its finish is the max, larger than $B$'s max.
• Case 2 — DFS enters $B$ first. The condensation is a DAG and the edge is $A\to B$, so there is no path $B⇝A$. DFS from $B$ therefore finishes all of $B$ without ever touching $A$. Later DFS starts inside $A$, so all of $A$ finishes after all of $B$.

Both cases give ${\max }_{A}f>{\max }_{B}f$: the SCC that is "upstream" in the DAG finishes later. This is exactly why picking the highest-finish vertex on the reversed graph lands you in a sink SCC there.

Graph (three vertices): $1\to 2,2\to 1,3\to 1.$ True SCCs: $\{1,2\}$ (mutual) and $\{3\}$ (nothing returns to $3$). Start DFS at 3: $disc=\{3:0\}$, stack $[3]$, onStack[3]=true.

• Edge $3\to 1$: $1$ unvisited ⇒ tree edge, recurse. $disc[1]=1$, stack $[3,1]$.
  • Edge $1\to 2$: recurse. $disc[2]=2$, stack $[3,1,2]$.
    • Edge $2\to 1$: $1$ is on the stack ⇒ back edge, $low[2]=\min (2,disc[1])=1$. Not a root. Return.
  • Back at $1$: tree edge returns $low[1]=\min (1,low[2])=1=disc[1]$ ⇒ root at 1, pop $\{2,1\}$. Now onStack[1]=onStack[2]=false — SCC $\{1,2\}$ is finished.
• Back at $3$: tree edge $3\to 1$ returns $low[1]=1$, so $low[3]=\min (0,low[1])=\min (0,1)=0=disc[3]$ ⇒ root at 3, pop $\{3\}$. SCC $\{3\}$. Correct result: $\{1,2\},\{3\}$.

Now make the bug bite. Reorder so the offending edge is a non-tree edge into an already-popped vertex. Take $1\to 2,2\to 1,2\to 3,3\to 1,$ starting at $1$: $\{1,2\}$ and $\{3\}$ are still the true SCCs.

• $disc=\{1:0,2:1\}$, stack $[1,2]$. From $2$: edge $2\to 1$ (on stack) ⇒ $low[2]=\min (1,disc[1])=0$. Then edge $2\to 3$: recurse, $disc[3]=2$, stack $[1,2,3]$.
  • From $3$: edge $3\to 1$. Is $1$ on the stack? Yes here, so both correct and buggy set $low[3]=\min (2,disc[1])=0$; $3$ is not a root, so $3$ gets glued to $\{1,2\}$ — but that is only because $1$ genuinely is on the stack (this graph really has $1,2,3$ all in one SCC via $2\to 3\to 1$).

The clean demonstration is the first graph run with the bug forced: if the code never checks onStack, then when we return to $3$ and see the finished vertex $1$ (already popped, onStack[1] should stop us), the buggy code still does $low[3]=\min (disc[3],disc[1])=\min (0,1)=0$? No — $disc[1]=1>0$, so it stays $0$. The genuine merge appears when a later vertex $w$ has an edge to a popped, smaller-disc vertex: min(low[w],disc[popped]) drops $low[w]$ below $disc[w]$, so $w$ never becomes its own root and its whole component fuses with the finished one. The onStack guard is precisely what forbids consulting a popped vertex.

SCCs: $X=\{1,2,3\}$ and $Y=\{4,5\}$. The only condensation edge is $X\to Y$ (from $3\to 4$). A topological order lists nodes so every edge points forward. Here the unique order is $X,Y$. Guarantee: in a topological order, for every edge $u\to v$, $u$ appears before $v$. This exists iff the graph is a DAG — which the condensation always is. So "SCC then topo-sort the condensation" is the standard recipe to impose a valid processing order on any cyclic directed graph.

First define the id convention. Tarjan emits an SCC (pops it) as soon as its root is found. Because a root is only recognised after everything it can reach has been explored and popped, sink SCCs of the condensation are emitted before source SCCs. If we number SCCs $0,1,2,\dots$ in emission order, then a larger id means "emitted later" = "closer to a source" = earlier in topological order. Equivalently, Tarjan's emission order is a reverse topological order of the condensation. This is exactly why the 2-SAT rule can read off truth values directly from ids without a separate topo-sort.

• Satisfiability check: $\text{id}[x]=2\ne 5=\text{id}[\neg x]$, so $x$ and $\neg x$ are in different SCCs ⇒ no contradiction for this variable.
• Assignment rule: set the literal whose SCC is emitted later (larger Tarjan id) to false, and its negation to true. Here $\text{id}[\neg x]=5>2=\text{id}[x]$, so $\neg x$ (larger id) is false, hence $x=\text{true}$. The key point: SCC membership decides satisfiability, SCC ordering decides the actual truth values.

Union-Find merges two elements whenever any connection exists between them; it only knows "connected or not," with no direction. If you union(u,v) for every directed edge $u\to v$, you get the weakly connected components (treat arrows as undirected) — which can be strictly larger than SCCs. Example: $1\to 2$ with no return edge puts $1,2$ in one Union-Find set but two different SCCs. Union-Find has no way to represent "reachable one way but not the other," so it cannot detect the mutual-reachability requirement. SCC needs the DFS ordering (Kosaraju/Tarjan); Union-Find is the wrong tool for directed cycles.

Let $r$ be the root of a DFS2 tree; it is the highest-finish unvisited vertex, so among all not-yet-assigned SCCs its own SCC $C$ has the largest max-finish. By L3.2's inequality, $C$ is a source in the (remaining) original condensation — no unassigned SCC has an edge into $C$. Reverse all edges: in $G^{\text{rev}}$, $C$ becomes a sink among unassigned SCCs — every edge from $C$ to another unassigned SCC now points into $C$. So a DFS from $r$ in $G^{\text{rev}}$:

1. Reaches every vertex of $C$ (because $C$ is strongly connected — reversing edges keeps it strongly connected).
2. Cannot escape to any other unassigned SCC (all their connecting edges now point inward).

Therefore the tree rooted at $r$ is exactly $C$. Remove it and repeat on the next-highest finisher. By induction every SCC is captured as one tree. ∎

1. Compute SCCs (Tarjan, $O(V+E)$). Give each vertex its SCC id.
2. Build the condensation DAG on the SCC ids ($O(V+E)$).
3. Topologically sort the DAG. For dense reachability, compute a reachability bitset per SCC in reverse topological order: $\text{reach}[C]=\{C\}\cup {\bigcup }_{C\to D}\text{reach}[D]$. This costs $O(V^2/64)$ with bitsets but answers each query in $O(1)$: "$u⇝v$?" $\equiv$ "$\text{id}[v]\in \text{reach}[\text{id}[u]]$".
4. Why SCCs first? Inside an SCC every vertex reaches every other, so all reachability questions collapse to the DAG level — far fewer nodes, and a DAG admits the clean topological DP above. Trying reachability on the raw cyclic graph would revisit cycles endlessly.

Correctness: $u⇝v$ in $G$ iff $\text{id}[u]⇝\text{id}[v]$ in the condensation, because SCC contraction preserves exactly the reachability relation.

(a) Self-loop $u\to u$. A single vertex $u$ is always trivially strongly connected to itself (the empty path reaches $u$ from $u$), so $\{u\}$ is an SCC whether or not the self-loop exists. The self-loop adds nothing to SCC structure.

• Kosaraju: DFS just marks $u$ visited on entry; the loop edge leads to an already-visited vertex and is ignored. $u$ ends up in its own tree unless a real cycle through other vertices includes it.
• Tarjan: edge $u\to u$ finds $u$ on the stack, so $low[u]=\min (low[u],disc[u])=disc[u]$ — no change. $u$ still satisfies $low[u]=disc[u]$ and is popped as the singleton SCC $\{u\}$. No infinite loop, because $u$ is already visited/onStack and we never recurse into a visited vertex. (b) Isolated vertex. It has no outgoing and no incoming edges.
• Kosaraju: the outer for each unvisited u loop eventually starts DFS1 at it; it finishes immediately. In DFS2 it forms a tree of size one ⇒ SCC $\{u\}$.
• Tarjan: the outer loop calls dfs(u); with no edges, immediately $low[u]=disc[u]$ ⇒ pop singleton SCC $\{u\}$. Takeaway: every vertex belongs to some SCC (at minimum itself). Both algorithms need an outer loop over all vertices precisely so isolated vertices and disconnected pieces are not missed.

Kosaraju needs which special order for the second pass? ::: Decreasing finish time on the reversed graph. Tarjan marks an SCC root when? ::: low[u] == disc[u], then pop the stack down to and including u. What is the role of onStack[u] in Tarjan? ::: A flag that is true while u is on the stack; it restricts low updates to the current unfinished component, so back edges into finished SCCs are ignored. Why can't Union-Find compute SCCs? ::: It only sees undirected connectivity; it cannot express one-way vs round-trip reachability. What SCC does an isolated vertex or a self-loop vertex form? ::: A singleton SCC containing just that vertex.