Split the directed graph into its strongly connected components and number them: the component holding the smallest node gets 0, the component holding the smallest node not yet numbered gets 1, and so on.
Write scc_labels(n, edges) returning a list of n labels, where entry i is the number of node i's component.
Examples
Input: n = 5, edges = [(0, 1), (1, 2), (2, 0), (3, 4)]
Output: [0, 0, 0, 1, 2]
Explanation: the triangle is component 0, then 3, then 4.
Input: n = 2, edges = [(1, 0), (0, 1)]
Output: [0, 0]
Constraints
1 <= n <= 2 * 10**4,0 <= len(edges) <= 10**5- The numbering must not depend on which order your search happened to visit nodes in.
Goals
- Return the components as a labelling rather than a count
- Choose a canonical numbering so the answer does not depend on the search order
- Keep the mapping from node to component for later use