787. Strong Groups
A city runs one-way shuttle services between n stops numbered 0 to n - 1. Each entry [u, v] in edges is a shuttle that carries riders from stop u to stop v, and it cannot be used in the opposite direction.
Two stops belong to the same group when a rider can travel from each stop to the other, changing shuttles as often as needed. Every stop is in a group with itself. Return the number of groups the stops split into. Duplicate shuttles and shuttles that start and end at the same stop may appear; they do not change the answer.
Example 1
- Input:
- n = 6, edges = [[4,2],[2,5],[5,4],[0,1],[1,3]]
- Output:
- 4
- Explanation:
Stops 4, 2 and 5 ride around a loop (4 to 2 to 5 and back to 4), so they form one group; stops 0, 1 and 3 sit on a one-way chain and each stands alone: 1 + 3 = 4 groups.
Example 2
- Input:
- n = 5, edges = [[3,0],[0,3],[1,4],[4,1],[0,1]]
- Output:
- 3
- Explanation:
Stops {0,3} can reach each other and so can {1,4}, but the shuttle 0 to 1 cannot be used backwards, and stop 2 has no shuttles at all: 3 groups.
Example 3
- Input:
- n = 3, edges = []
- Output:
- 3
- Explanation:
With no services every stop is alone, giving 3 groups.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ edges.length ≤ 2 * 105
- 0 ≤ u, v < n for every
[u, v]
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 300 msC++ 75 msJava 150 msJavaScript 150 msTypeScript 150 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)