Mutual Reach Groups
Problem
A directed graph has n nodes numbered from 0 and a list of one-way edges (u, v). Split the nodes into groups so that two nodes share a group exactly when each can reach the other by following edges. Return the groups, each sorted ascending, with the list of groups sorted as well. A node that reaches nobody and is reached by nobody still forms a group of its own.
Examples
Input: n = 5, edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)]
Output: [[0, 1, 2], [3], [4]]
Why: 0, 1 and 2 form a loop; 3 and 4 can never get backInput: n = 4, edges = [(0, 1), (1, 0), (2, 3), (3, 2), (1, 2)]
Output: [[0, 1], [2, 3]]
Why: the edge 1 -> 2 runs one way only, so the pairs stay apartInput: n = 1, edges = []
Output: [[0]]
Why: edge case, a lone node is its own groupHints
0 / 3
Checking every pair of nodes for reachability in both directions works for tiny graphs but repeats a search per pair. Look for a way that needs only a couple of full traversals.
Reversing every edge keeps each group exactly the same, because mutual reachability does not care about direction. What it does change is which groups you can wander into from outside.
Run a depth-first search on the original graph and record nodes in the order they finish. Then walk that order from last to first on the reversed graph; each search that starts on an unclaimed node claims exactly one group.
Solution
This is Kosaraju's two-pass method. The first depth-first pass records nodes by finishing time, and the node that finishes last always belongs to a group that no other group can reach. The second pass runs on the reversed graph in reverse finishing order: from such a node the reversed edges lead only into its own group, so each search collects one group and nothing more. Sorting at the end makes the output order fixed. Time is O(n + m) for the passes plus the final sort, and space is O(n + m).
def reach_groups(n, edges):
fwd, back = [[] for _ in range(n)], [[] for _ in range(n)]
for u, v in edges: fwd[u].append(v); back[v].append(u)
order, seen, owner = [], [False] * n, [None] * n
def finish(u): # pass 1: record nodes as they finish
seen[u] = True
for v in fwd[u]:
if not seen[v]: finish(v)
order.append(u)
def claim(u, group): # pass 2: reversed edges cannot leave the group
owner[u] = group; group.append(u)
for v in back[u]:
if owner[v] is None: claim(v, group)
for u in range(n):
if not seen[u]: finish(u)
groups = []
for u in reversed(order): # latest finisher first
if owner[u] is None: groups.append([]); claim(u, groups[-1])
return sorted(sorted(g) for g in groups)
print(reach_groups(5, [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)])) # -> [[0, 1, 2], [3], [4]]
print(reach_groups(4, [(0, 1), (1, 0), (2, 3), (3, 2), (1, 2)])) # -> [[0, 1], [2, 3]]
print(reach_groups(1, [])) # -> [[0]]Stuck on the idea rather than the code? Strongly Connected Parts covers it.