Every group, in order

Split all n junctions into their strongly connected groups. Return a list group with one number per junction. Two junctions get the same number exactly when each can reach the other. Number the groups 0, 1, 2, … with no number missing, and in an order that every street respects: for every street (u, v), group[u] <= group[v]. That order is a topological order of the graph of groups (lesson 1).

streets = [(0, 1), (1, 4), (4, 0), (5, 4), (5, 6),
           (1, 2), (2, 3), (3, 7), (7, 6), (6, 2)]
scc(8, streets)   # [1, 1, 2, 2, 1, 0, 2, 2]
scc(4, [(2, 3), (0, 1), (1, 2)])   # [0, 1, 2, 3]

When several numberings are right (groups with no street between them can come in either order), any of them is accepted. The tests check the numbers you return: the groups, the order, and no gaps.

Limits

• Up to 100,000 junctions and 160,000 streets.
• The search can go 100,000 levels deep. The big tests have 4 seconds each.