A strongly connected 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.

Run one DFS (depth-first search) and give each node a number, disc, in the order the search reaches it. Push the node on group_stack. A node on group_stack is waiting: it was reached, but its group is not complete.

low[node] is the smallest disc of a waiting node that the subtree of node can reach. The search lowers it with an edge to a node that still waits, and with the low of a finished child.

When node has no edge left, compare low[node] with disc[node]. If they are equal, nothing in the subtree of node can climb to a waiting node older than node. So node is the first node of its group that the search reached.

Every node above node on group_stack was reached through node, so node reaches it. None of those nodes is a first node of its own group, so each one climbs to an older waiting node, and the climbs end at node. They reach node back. That makes them one group, and the search pops group_stack down to node.

Example: in 1 -> 2, 2 -> 1, 2 -> 3, the search goes 1, 2, 3. Node 3 has no edge left and low[3] = disc[3] = 3, so it forms the group {3}. Node 2 has the edge back to node 1, so low[2] = 1. Node 1 ends with low[1] = disc[1] = 1, and it pops {2, 1}.

The board uses 7 cities. The groups are {1, 2, 3}, {4, 5, 6} and {7}. The flights are 1 -> 2, 2 -> 3, 3 -> 1, then 3 -> 4, then 4 -> 5, 5 -> 6, 6 -> 4, then 7 -> 4.

The search goes 1, 2, 3. The flight 3 -> 1 leads to city 1, which waits on group_stack, so low[3] becomes 1. Then the search goes 4, 5, 6, and the flight 6 -> 4 makes low[6] equal to 4.

City 6 finishes with low[6] = 4, which is not disc[6] = 6, so it stays on the stack and hands 4 to city 5. City 5 does the same for city 4. City 4 finishes with low[4] = disc[4] = 4, so group_stack is popped down to 4. The group {4, 5, 6} gets comp_id 0.

Cities 3 and 2 finish with low 1, and hand it up. City 1 finishes with low[1] = disc[1] = 1, so the stack is popped down to 1. The group {1, 2, 3} gets comp_id 1.

Then a new search starts at city 7. Its flight 7 -> 4 leads to city 4, which is already in group 0. Here on_stack[4] is False, so disc[4] = 4 is not used, and low[7] stays 7. City 7 forms the group {7} with comp_id 2.

There are 3 groups, so the answer is NO. Group 0 was completed first. No flight leaves it, so no route leads from city 6 to city 7. The answer is ["NO", 6, 7], and the final comp is [1, 1, 1, 0, 0, 0, 2].

The first trap is the test if on_stack[nxt]:. A neighbour that was reached but is not on group_stack is in a group that is already complete. It cannot reach node, so its disc must not lower low[node].

On the board graph, leave the test out. City 7 sees city 4, and low[7] becomes 4. Now low[7] is not disc[7], so city 7 is never popped. The result is comp = [1, 1, 1, 0, 0, 0, -1], and city 7 has no group.

The smallest example is n = 2 and edges = [[2, 1]]. City 1 forms its own group first. City 2 then sees city 1 and takes low[2] = 1, so city 2 is never popped. Only one group is counted, and Flight Routes Check would answer ["YES"] where the right answer is ["NO", 1, 2].

The second trap is the flag. on_stack[node] must become False only when node is popped with its group, not when the search leaves node. A node can wait on group_stack long after the search has left it. For n = 3 and edges = [[1, 2], [2, 1], [1, 3], [3, 2]], an early clear gives [1, 1, 0], two groups. The right answer is [0, 0, 0].

The third trap is the last step of a finished node: low[parent] = min(low[parent], low[node]). On the board graph, without it the result is [3, 2, 2, 1, 0, 0, 4], five groups instead of three.

The search is iterative, with path holding (node, iterator). Flight Routes Check allows 10^5 cities in one chain. A recursive dfs would nest 10^5 calls. With Python's default limit, a chain of 2000 cities already raises RecursionError.

Each city is pushed on group_stack once and popped once. Each flight is read once by the iterator of its city. The time is O(V + E). adj, disc, low, on_stack, comp, group_stack and path hold one entry per city or per flight, so the space is O(V + E).

On the board graph, 7 cities and 8 flights give 7 pushes, 7 pops and 8 flight reads.

Strongly Connected Components (Kosaraju) finds the same groups with two searches and a reversed copy of the graph. The first search records the finish order. The second search reads that order from the end and walks the reversed graph.

Tarjan's algorithm needs one search over the original graph, and no reversed copy. It needs two extra arrays, low and on_stack, and a stack of waiting nodes. Both algorithms cost O(V + E).

The group ids come out in opposite orders. Kosaraju numbers a group that no edge enters first. Tarjan numbers a group that no edge leaves first. Every edge between two groups goes from a higher comp_id to a lower one in Tarjan's output.

The undirected cousin of this card is Tarjan's Bridges. It uses the same disc and low, but it needs no stack, because an undirected search has no edge between two different subtrees. If the graph is undirected and you only count pieces, a plain search or union-find is enough.