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

Step 1 — What a "one-way road" graph even is

WHAT. A directed graph is dots (call them vertices or nodes) joined by arrows (edges). An arrow $u \to v$ means "you may travel from $u$ to $v$ ", but not back, unless a separate arrow $v \to u$ also exists.

WHY start here. The entire idea of an SCC lives or dies on direction. In an undirected road you can always turn around; here you cannot. So "can I get there" and "can I get back" are two different questions — that difference is the whole subject.

PICTURE. Below, the arrow from $A$ to $B$ is coral. You can slide along it left-to-right. There is no arrow back, so from $B$ you are stuck: you cannot return to $A$ . That one-way-ness is everything.

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

Step 2 — The example graph and its two hidden "clubs"

WHAT. Our running graph has vertices $1, 2, 3, 4, 5$ and edges $1 \to 2, 2 \to 3, 3 \to 1, 3 \to 4, 4 \to 5, 5 \to 4.$

WHY this one. It hides exactly the two structures we need to explain: a 3-cycle ${1, 2, 3}$ (round trips everywhere inside) and a 2-cycle ${4, 5}$ , joined by the one-way bridge $3 \to 4$ . That bridge is the trap-door: you can go from the first club to the second, but never back.

PICTURE. The lavender loop $1 \to 2 \to 3 \to 1$ is one club; the mint loop $4 ⇄ 5$ is the other. The single coral arrow $3 \to 4$ leaks forward only.

Step 3 — "Finish time": when DFS truly leaves a node

WHAT. Run a Depth-First Search: dive as deep as you can along arrows, and only when a node has no unexplored arrows left do you declare it finished and step back. The moment you step back off a node is its finish time $f (u)$ — a tick on a clock, counting up.

WHY finish time and not visit time. We need a number that says "this node's entire forward-reachable region is done." Visit time (when you arrive) does not know what lies ahead. Finish time is stamped after every descendant is buried — so a node with a big finish time was the entrance to a lot of stuff, or the last thing explored. That "who wraps up last" ordering is the pivot of the whole proof.

PICTURE. Watch DFS from $1$ : it plunges $1 \to 2 \to 3 \to 4 \to 5$ . Node $5$ dead-ends (its only arrow $5 \to 4$ leads to an already-visited node), so $5$ finishes first. Then $4$ , then $3$ , then $2$ , then $1$ . Finish stamps grow as we back out.

Step 4 — The key law: earlier club finishes later

WHAT. Group the finish times by club. Take any two SCCs $A$ and $B$ where the condensation has an arrow $A \to B$ ( $A$ can reach $B$ , $B$ cannot reach $A$ ). Then the latest finisher in $A$ beats the latest finisher in $B$ : $max_{u \in A} f (u) > max_{v \in B} f (v) .$

WHY it holds (two cases, both must be covered).

Case 1 — DFS enters $A$ first. Since $A$ reaches $B$ , the search dives all the way through $B$ before backing out of the node where it first entered $A$ . That entry node therefore finishes after everything in $B$ . So $A$ 's max finish $>$ $B$ 's max finish. ✓
Case 2 — DFS enters $B$ first. Because the condensation is a Directed Acyclic Graph (DAG), there is no path $B ⇝ A$ . DFS started in $B$ finishes all of $B$ without ever touching $A$ . Only later does a fresh DFS begin in $A$ , finishing after $B$ . Again $A$ 's max $>$ $B$ 's max. ✓

PICTURE. Two finish-time bars: club $A = {1, 2, 3}$ (lavender) sits entirely higher on the finish clock than club $B = {4, 5}$ (mint). The one-way arrow points $A \to B$ ; the finish heights point the opposite way.

Step 5 — Flip every arrow: source becomes sink

WHAT. Build $G^{rev}$ : keep the vertices, reverse every edge. Our edges become $2 \to 1, 3 \to 2, 1 \to 3, 4 \to 3, 5 \to 4, 4 \to 5.$

WHY reverse. Inside a club, reversing arrows changes nothing — a round trip reversed is still a round trip, so the clubs are identical in $G^{rev}$ . But between clubs the leak flips: the trap-door $3 \to 4$ becomes $4 \to 3$ . The club that was a source (only outgoing bridges) is now a sink (bridges point into it). A DFS launched inside a sink club cannot escape — every bridge out has been turned into a bridge in.

PICTURE. Same two loops (unchanged), but the coral bridge now points $4 \to 3$ , into the ${1, 2, 3}$ club. Standing in ${1, 2, 3}$ in $G^{rev}$ , all exits are sealed.

Step 6 — Second DFS, in decreasing finish order

WHAT. Reverse the finish sequence $5, 4, 3, 2, 1$ to get processing order $1, 2, 3, 4, 5$ — i.e. largest finish time first. Now DFS on $G^{rev}$ , taking the first still-unvisited node in that order as each new root. Each DFS tree = one SCC.

WHY largest-first. By Step 4, the largest finish time sits in a source club of the original graph = a sink club of $G^{rev}$ (Step 5). Starting there, we are stuck inside that sink club (exits sealed) yet reach all of it (it's strongly connected). One tree, one club. Erase it; the next unvisited largest-finisher is a source-of-what-remains, and the same argument repeats.

PICTURE. Start at $1$ . In $G^{rev}$ : $1 \to 3 \to 2$ , and $2 \to 1$ closes the loop — tree ${1, 2, 3}$ . The bridge $4 \to 3$ points toward us, so we never walk out to $4$ . Next unvisited is $4$ : $4 \to 5$ , $5 \to 4$ — tree ${4, 5}$ .

Step 7 — The degenerate cases (never leave a scenario unshown)

WHAT. Corner cases the recipe must survive:

A single node with no edges. DFS1 visits it, finishes it alone. Reverse graph: still isolated. DFS2 tree = ${u}$ — a valid SCC of size 1. ✓
A self-loop $u \to u$ . Doesn't create a bigger club; $u$ is trivially mutually reachable with itself. Still one SCC ${u}$ . ✓
A whole graph that is one big cycle ( $1 \to 2 \to \dots \to 1$ ). Every node reaches every other both ways → one SCC containing all. DFS2 from the top finisher never seals off anything smaller, so a single tree swallows the graph. ✓
A pure Directed Acyclic Graph (DAG) (no cycles at all). No round trips anywhere → every node is its own SCC. DFS2 grows $V$ separate one-node trees. ✓

WHY show these. A learner will meet all of them. The law of Step 4 and the sealing of Step 5 hold regardless of these shapes — because they were proven from "condensation is a DAG", which is true even when the DAG is the whole graph (last case) or a single point (first case).

PICTURE. Four mini-graphs: isolated dot, self-loop, one giant cycle, and a 3-node DAG chain — each labelled with how many SCCs it yields.

The one-picture summary

Everything above, compressed: DFS1 stamps finish times (source club finishes highest) → reverse the arrows (source becomes sealed sink) → DFS2 from highest-finisher peels off one sealed club at a time. Two passes, linear time $O (V + E)$ , exact SCCs.

Recall Feynman retelling — the whole walk in plain words

Picture cities joined by one-way roads. Take a long tour and, each time you fully finish exploring everything reachable from a city, write its name on a list. The city you finish last is special: it sits in a "club" that can reach lots of places but that nothing upstream points back into — a source club. Now do the mischievous thing: flip every road. Round trips inside a club still work (a loop reversed is still a loop), but the one-way bridges between clubs now point backwards, so that source club becomes a dead-end sink — once you drive in, you can't drive out. Start a fresh tour from the last-finished city on the flipped map: you roam all of its club and, because every exit road now points inward, you can't leak into any other club. That one tour is exactly one SCC. Cross those cities off, look for the next-highest finisher still unvisited, repeat. Every tour fences off precisely one club. That's Kosaraju: knock twice, reverse, order by finish.

Recall Quick self-test

Why must DFS2 process in decreasing finish time? ::: Because the highest finisher lies in a source SCC of $G$ = a sink SCC of $G^{rev}$ , so its DFS tree cannot escape into another SCC; any other order breaks this seal. After reversing, why do the clubs themselves stay the same? ::: Inside an SCC every path has a reverse partner already, so reversing all arrows leaves mutual reachability untouched; only the between-club bridges flip. On a pure DAG, how many SCCs does Kosaraju report? ::: Exactly $V$ — every vertex is its own SCC, so DFS2 grows $V$ single-node trees.

Related tools worth linking in your head: Topological Sort on the condensation, Bridges and Articulation Points-style low-link bookkeeping, 2-SAT (built directly on SCCs), and Union-Find for a different notion of grouping. See the parent: SCC parent note.