Two vertices of a digraph are in the same strongly connected component when each can reach the other. That is an equivalence relation, so it partitions the vertices, and the partition can be computed from two depth-first walks: one on the graph to get a finishing order, and one on the reversed arcs taking the vertices in that order. Collapsing each component to a point always gives an acyclic digraph, which is what the whole construction is for.
Core ideas
The hard idea is why the second pass runs on the reversed arcs. The relation and the condensation are the setup for it.
Write u ~ v when there is a path from u to v and a path from v to u. It is reflexive by the empty path, symmetric by its own statement, and transitive by concatenating paths, so it is an equivalence relation and its classes partition the vertices. The lab computes those classes twice: once by the two-pass algorithm and once straight from the definition, by testing reachability from every vertex to every other, and compares the two partitions.
Collapse each component to a single point and keep an arc between two points when some arc ran between their components. The result cannot have a cycle: a cycle among components would make every vertex on it mutually reachable with every other, so they would all have been one component. On the lab's opening graph the seven vertices collapse to three points joined in a line, and the panel reports the condensation acyclic rather than assuming it.
The vertex that finishes last in the first walk lies in a component that nothing points into — a source of the condensation. Walking forwards from there would reach everything downstream and swallow several components at once. Walking the REVERSED arcs from there reaches exactly its own component, because the arcs into the component became arcs out of it and lead nowhere in the reversed graph. The lab checks the claim by reporting the in-degree of that component in the condensation, and it is 0.
The material
The relation, the algorithm, the reason the reversal is necessary rather than convenient, and the independent check.
A strongly connected component of a digraph is a maximal set of vertices in which every vertex reaches every other. Maximal matters: a single vertex is always mutually reachable with itself, so without maximality every vertex would be its own component and the definition would say nothing.
The classes of the relation are those maximal sets, so nothing further has to be checked: partition and maximality come together. The brute-force method is the definition made mechanical — compute reachability from every vertex, then group u with v when each appears in the other's set — and that is what the lab runs beside the fast method.
Nothing about step 3 is arbitrary and everything about it is fragile. Taking the vertices in increasing finish order, or walking the original arcs in the second pass, both produce something — a partition of the vertices — and neither produces the components. The lab's independent check is the only thing on the page that can tell the difference.
Let v have the largest finish time of a depth-first walk on a digraph. Then the component containing v has in-degree 0 in the condensation: no arc enters it from another component.
Suppose an arc ran from a component B into the component A of v, and let b be its tail. Since the condensation is acyclic, no path returns from A to B.
Consider which of A and B the walk enters first. If it enters B first, then from inside b it can reach A along that arc, so every vertex of A is discovered inside the call at b and finishes before it, making f[b] > f[v]. If it enters A first, then it cannot reach B at all from A, so B is untouched while A finishes, and b is discovered afterwards, again giving f[b] > f[v].
Either way something finishes later than v, contradicting the choice of v. So no such arc exists.
□
That theorem is the whole design. Standing in a source component and following the reversed arcs, everything reachable is inside the component: the reversed arcs that would take you out of it are the forward arcs that came in, and there are none. So the second pass's first tree is exactly one component. Remove it and the remaining condensation still has the same property, so the argument repeats.
The lab opens on 1>2, 2>3, 3>1, 3>4, 4>5, 5>6, 6>4, 5>7. The first walk finishes the vertices in the order that makes the decreasing list 1 2 3 4 5 7 6. The second pass, on the reversed arcs, produces the components {1, 2, 3}, {4, 5, 6} and {7}. The condensation has three points and two arcs, in a line, and is acyclic. Mutual reachability computed from the definition returns the same three sets, and the panel prints both partitions.
Two things in that example are easy to misread. The vertex 7 is its own component not because it is isolated — 5 points at it — but because nothing comes back from it. And the decreasing finish list puts 7 before 6 even though 6 is lower-numbered, because the walk reached 6 first from 5 and closed it before it ever opened 7.
A single cycle through every vertex is one component: on 1>2, 2>3, 3>4, 4>1 the lab reports one component of four vertices, and a condensation that is a single point with no arcs. An acyclic digraph is the other extreme: on 1>2, 2>3, 1>3, 3>4 every vertex is its own component, there are four of them, and the condensation is the graph itself. Those are the two cases where the second pass has the least to do, and running them is the fastest way to convince yourself the algorithm is not doing something else.
The counts, beside the bound. On the opening graph the second pass reports 7 vertex visits and 8 arc reads; on the four-vertex cycle, 4 and 4; on the acyclic preset, 4 and 4. Each is V and E for that graph. The bound is that the whole algorithm is Θ(V + E), and it is two walks plus a reversal: the reversal itself is one pass over the arcs, and neither walk visits a vertex twice. What the measurement cannot show is that no input makes it worse, and that is what the argument is for.
Interactive
The finish order names a source component, which is why the second pass runs on the transpose
Method
The first pass produces a schedule. The second pass consumes it, backwards.
Nothing else from that walk is used — not its forest, not its edge classes. Record the closing order and then put the walk aside; the list of vertices in decreasing finish time is the only output the second pass reads.
Reversing is Θ(E) and doing it lazily, by scanning for arcs that point at the current vertex, turns a linear algorithm into a quadratic one. Build the reversed arc list once.
Each new tree of the second pass begins at the undiscovered vertex that finished LATEST in the first pass. Falling back on the lowest-numbered undiscovered vertex is the single change that quietly breaks this algorithm: it still terminates, still partitions the vertices, and no longer computes components.
It is Θ(E) and it is the thing most downstream work actually wants. If it has a cycle, the components are wrong — that check is free and it catches the previous step having gone astray.
The arcs are 1>2, 2>3, 3>1, 3>4, 4>5, 5>6, 6>4, 5>7. Arcs out of a vertex are taken in the order they were typed.
Watch what the reversal bought at the very first step. Walking forwards from 1 would have reached all seven vertices and returned one component. Walking backwards from 1 reached exactly three, because the arc 3>4, which is the only way out of that component, became 4>3 and points inwards.
Watch also the start at 4. In the reversed graph the arc 4>3 exists and leads straight into a finished component; the walk simply finds 3 already discovered and stops, which is why no special handling is needed for arcs between components. The schedule guarantees that any component reached this way is already complete.
For a faded rehearsal, add the arc 7>5 to the original graph and predict the new components before running it. The supplied first move is this: 5 already reaches 7, so the new arc makes 5 and 7 mutually reachable, and 7 joins whatever 5 is in. Say what the three components become, how many points the condensation then has, and whether it is still acyclic.
You should be able to produce the finishing order from the first walk, reverse the arcs, take the starts from the schedule rather than from the numbering, build the condensation, and state the theorem about the last-finishing vertex that makes the whole thing work.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.