Strongly connected components: two searches, the second backwards

In a town of one-way streets, driving from the station to the market doesn't mean you can drive back. Some junctions form a tangle where you can get from any of them to any other and home again; leave it by the wrong street and there may be no way back in.

Those tangles are a directed graph's strongly connected components: the largest groups of nodes that can all reach each other. A plain depth-first search can't pick one out: from a node it reaches everything downstream, including nodes with no way back. Kosaraju's algorithm uses two searches, the second with every edge turned round; Tarjan's manages with one.

strongly connected

Nodes u and v are strongly connected when a path leads from u to v and another leads back.

strongly connected component (SCC)

A largest group of nodes that are all strongly connected. Every node is in exactly one; a node on no cycle is a component by itself.

condensation

Each SCC squashed into one node, with an edge wherever an edge joins two components. It has no cycles: it is a DAG.

source and sink

A source component has no edges coming in from other components; a sink has none going out.

finishing order

The order a depth-first search finishes nodes in: each after every node its search went on to discover.

reversed graph

Every edge turned round. A path from u to v becomes one from v to u, so the SCCs stay the same.

This graph has three components: A, B and C; D, E and F; G and H. B → D and G → F lead into D, E and F, and no edge leads out of them. Neighbours are taken in alphabetical order. In the first pass, each node goes on top of S as it finishes.

A node finishes only after everything its search discovers, so D, E and F finish before B, which led into them. Nothing from A reaches G, so the loop starts a second search there, and G finishes last.

That last finisher always lies in a source component, one that no other component points into. Suppose a component X had an edge into G's. If the first pass entered X first, it reached G's component from there and finished all of it before backing out of X. If it entered G's first, it could never reach X (or the two would be one component), so it finished G's before visiting X. Either way a node of X finishes after G.

Now reverse every edge. Components keep their members, but the edges between them turn round, so the source becomes a sink: a search from G can reach only G's own component. Each later search starts from the latest finisher still unplaced, whose component is a source of what remains, so its reversed edges out lead only to components already placed. The search skips those, which is why D's search turned back at B and G.

The components come out sources first, a topological order of the condensation. Each pass reads every node and edge once (16 node visits and 20 edges examined here), and building the reversed adjacency lists is one more sweep: O(V + E) in all.

Six nodes, typed in as A>B, B>A, C>A, C>D, D>E, E>C, E>F. The first pass plays without questions: work out the finishing order and check it against S. Then predict which node is popped next, and whether each node the backwards search meets joins the current component.

The first search began at A, but A and B form a sink, so they finished early. C finished last, in the source component C, D and E: where the first pass starts doesn't matter.

Here is the first pass on four nodes: A and B point at each other, so do C and D, and C → A joins the pairs. finished records each node as it finishes, and the loop at the bottom starts a search from every node not yet seen.

def dfs(graph, u, seen, finished):
    seen[u] = True
    for v in graph[u]:
        if v not in seen:
            dfs(graph, v, seen, finished)
    finished.append(u)

graph = {'A': ['B'], 'B': ['A'], 'C': ['A', 'D'], 'D': ['C']}
seen = {}
finished = []
for u in graph:
    if u not in seen:
        dfs(graph, u, seen, finished)
print(' '.join(finished))

So the second pass starts at C, and the reversed edges matter as much as the order.

Tarjan's algorithm finds the same components in one search. Each node gets an index, its place in the visit order, and a low-link: the smallest index it can get back to through the search tree below it plus one more edge, counting only nodes still on a stack S, where nodes stay after they finish until their component is known. A node that finishes with its low-link equal to its index roots a component: pop S down to it, and those nodes are one SCC.

Components close sinks first, where Kosaraju's came out sources first. G → F is ignored: F's component is finished and can't reach back to G. Its extra memory is O(V); Kosaraju's reversed copy of the edges needs O(V + E).

The condensation never has a cycle (its components would merge), so SCCs are a common first step. Packages in one component of a dependency graph depend on each other in a loop and must be built together; a topological sort of the condensation orders the groups. In a follow network, a component is a group of accounts that all reach each other. A 2-SAT solver turns each clause “a or b” into edges not-a → b and not-b → a: the clauses can all hold exactly when no variable shares a component with its negation.

A reaches every node of that DAG, and still every node is alone.

The opposite slip splits one component in two.

• A strongly connected component is a largest group of nodes that all reach each other. Every node is in exactly one, a node on no cycle is alone, and reaching one way isn't enough.
• Squash each component to a node and the condensation is a DAG, which topological sort can order.
• Kosaraju's: the last node a DFS finishes lies in a source component. Reverse every edge and pop nodes in reverse finishing order: each search of the reversed graph collects exactly one SCC, sources first.
• Tarjan's: one DFS that gives each node an index and a low-link. A node whose low-link equals its index roots a component, popped off the stack in one go, sinks first.
• Both are O(V + E) with adjacency lists. SCCs find dependency cycles, groups in follow networks and 2-SAT answers.
• Practise with Can Every Course Be Taken?, where a cycle means a component of two or more courses, and Course Order; write the search in Write depth-first search, or try your own graphs in the Kosaraju and Tarjan visualisers.