1074. Mutual Reach Groups
A region has n towns numbered 0 to n-1 and a list of one-way roads: edges[i] = [u, v] means you can drive from town u to town v, but not back along the same road. Roads may repeat, and a road may lead from a town to itself.
Two towns belong to the same mutual reach group when you can drive from each of them to the other, possibly passing through other towns. Every town lies in exactly one group; a town that cannot be part of any round trip with another town forms a group on its own.
Return all groups. Each group must be listed in ascending order of town number. The order of the groups in the answer does not matter.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[2,0],[3,4]]
- Output:
- [[0,1,2],[4],[3]]
- Explanation:
Towns 0, 1, 2 can reach each other around the triangle; the one-way road 3→4 gives towns 3 and 4 a group each.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output:
- [[3],[2],[1],[0]]
- Explanation:
All roads point forward, so nobody can come back and every town is a group by itself.
Example 3
- Input:
- n = 6, edges = [[0,1],[1,0],[1,2],[2,3],[3,2],[4,5]]
- Output:
- [[2,3],[0,1],[5],[4]]
- Explanation:
Towns 0 and 1 are linked both ways, so are 2 and 3; the road 1→2 only goes one way and does not merge the two pairs.
Constraints
1 ≤ n ≤ 5 * 104
0 ≤ edges.length ≤ 105
edges[i].length == 2
0 ≤ edges[i][j] < n
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)