A strongly connected component, or group, is a set of nodes in a directed graph where each node can reach every other node of the set. Two nodes are in one group exactly when each can reach the other.

If you collapse each group into one point, the groups form a graph with no cycle. Every edge between two groups goes one way. A group that no edge enters is a source group. A group that no edge leaves is a sink group.

Pass 1 runs a DFS (depth-first search) on adj and adds a node to order when it finishes. One fact makes this useful. If an edge leads from group A to a different group B, then the node of A that finishes last finishes after every node of B.

The reason has two cases. If the search enters A first, it reaches all of B before the first node of A finishes. If the search enters B first, it cannot reach A, because that would make A and B one group. So B is completely finished before A is entered. In both cases A finishes later.

So the node at the end of order is in a source group, and no other group leads into it. Pass 2 walks radj, the graph with every edge reversed, from that node. Reversed edges lead from a node to the nodes that can reach it, so the walk finds this group and nothing else.

Example: in the graph 1 -> 2, 2 -> 1, 2 -> 3, the groups are {1, 2} and {3}. The node 3 finishes first. The last node in order is in {1, 2}, and the reversed walk from it reaches only node 1 and node 2.

The board uses 8 planets, as in Planets and Kingdoms (CSES 1683). The groups are {6, 7, 8}, {3, 4, 5}, {2} and {1}. The edges are 6 -> 7, 7 -> 8, 8 -> 6, then 8 -> 3, then 3 -> 4, 4 -> 5, 5 -> 3, then 5 -> 2, then 2 -> 1.

Pass 1 starts a search at 1, then at 2, then at 3, then at 6. The start loop runs from 1 to n, so it starts a new search at each node that is not visited yet. The finish order is order = [1, 2, 5, 4, 3, 8, 7, 6].

Pass 2 reads order from the end. The first node is 6. The search on radj reaches 8 and 7, because they can reach 6. The group {6, 7, 8} gets comp_id 0.

The next node with no group is 3. In radj[3], node 8 already has a comp_id, so the search does not go there. It reaches 5 and 4. The group {3, 4, 5} gets comp_id 1. Then node 2 gets 2, and node 1 gets 3.

The answer is comp = [3, 2, 1, 1, 1, 0, 0, 0] for planets 1 to 8. Every edge between two groups goes from a lower comp_id to a higher one. For example, 8 -> 3 goes from 0 to 1.

The second pass must walk radj. If it walks adj, the search from node 6 follows every edge forwards and reaches every planet downstream. On the board graph the result is comp = [0, 0, 0, 0, 0, 0, 0, 0]: one group, which is wrong.

The second pass must read order from the end, with reversed(order). If it reads order from the start, the first node is 1, which is in a group that other groups lead into. On the board graph, this also gives eight zeros.

A node must be added to order when it finishes, which is when it has no unvisited neighbour left. If you add it when it is first visited, order records discovery order, and the finish-time fact no longer applies.

Example: for n = 3 and edges = [[1, 2], [2, 1], [2, 3]], the correct answer is [0, 0, 1]. Walking adj in pass 2 gives [0, 0, 0], and so does reading order forwards.

The first pass is iterative, with stack holding (node, iterator). Planets and Kingdoms allows 10^5 planets in one chain. A recursive dfs would nest 10^5 calls and pass Python's recursion limit.

Pass 1 reads every edge of adj once, and pass 2 reads every edge of radj once. The time is O(V + E). adj, radj, visited, order, comp and stack hold one entry per node or per edge, so the space is O(V + E).

On the board graph, 8 nodes and 9 edges give 9 forward entries and 9 reversed entries, 18 in total.

The ids come out in topological order of the groups, because pass 2 starts in a source group and later passes start in groups it leads to. This is why comp can also order the groups.

If the graph is undirected, reachability is already symmetric, so union-find or a plain search finds the groups, as in Redundant Connection (LC 684) or Number of Provinces (LC 547). If you need the edges whose removal splits an undirected graph, use Critical Connections in a Network (LC 1192). Kosaraju is needed only when the edges have a direction.

Tarjan's algorithm finds the same groups in one pass with disc and low. Kosaraju uses two passes, and its reason is easier to state, so many interviews prefer it.