🧭 Conceptual Foundation & Pattern Intuition

Kosaraju's algorithm finds every strongly connected component of a directed graph with two depth-first passes. The first pass walks the graph as given and records each node's finish order: the order in which a DFS runs out of unvisited neighbors to descend into. The second pass walks the transpose graph -- every edge reversed -- starting from unvisited nodes in decreasing finish order. Each tree the second pass grows is exactly one strongly connected component, because a node that finished late in the first pass has nothing left unexplored beneath it, so it is a "source" of whatever graph structure remains, and walking the transpose from a source reaches precisely the nodes that can also reach it back in the original graph.

🌌 The Analogy: Draining a Reservoir System From the Lowest Outlet

Picture a network of reservoirs connected by one-way spillways. The first pass is a survey: starting anywhere, follow spillways downstream and note, for each reservoir, the moment you have nothing left downstream of it to explore -- reservoirs that are true dead ends (or whose whole downstream network is already surveyed) get noted first. The second pass works backward: starting from the LAST reservoir noted (the one truly furthest downstream, still unassigned), follow the spillways upstream instead. Every reservoir reached this way can flow downstream back to the start (that is how you reached it walking upstream), and the start can flow to all of them too, since they were reachable walking downstream in the first pass restricted to this same neighborhood -- so they are one kingdom, drained together. Moving to the next unassigned reservoir (again picking the latest-noted one) always starts a fresh kingdom, because every reservoir it could drain into upstream is already claimed.

🪄 Breaking Down the Code's "Magic Trick"

for planet in reversed(order):        # decreasing finish time: always a source of what's left
    if kingdom[planet] != -1:
        continue
    kingdom_id += 1
    kingdom[planet] = kingdom_id
    stack = [planet]
    while stack:
        u = stack.pop()
        for v in radj[u]:              # the TRANSPOSE graph, not adj again
            if kingdom[v] == -1:
                kingdom[v] = kingdom_id
                stack.append(v)
 

Two things have to both be true for this to work. First, reversed(order) -- processing late finishers first -- guarantees each new component's starting planet has no edge, in the original graph, into any component that hasn't been found yet; if a lower-finishing planet were picked instead, its component could still have an edge into a not-yet-discovered one, and the walk would wrongly reach across that boundary. Second, radj: walking the transpose from that starting planet reaches every planet that can reach IT in the original graph. Combined with the fact those planets are also reachable FROM it (they finished no later, in the same downstream neighborhood surveyed in pass one), the set found is exactly the group that can reach each other both ways -- a kingdom.

💡 Summary

Two O(V + E) depth-first passes -- one to order nodes by how "finished" they are, one on the reversed graph in that order -- peel every strongly connected component off a directed graph in linear time, with no extra structure beyond the two adjacency lists and a visited/component array.