700. Directed Loop Check
A task runner has n jobs numbered 0 to n - 1 and a list edges where each pair [u, v] means job u must finish before job v can start. Return true if the jobs can never all finish because some chain of dependencies leads back to a job that is already waiting, and false otherwise.
The list may contain repeated pairs and pairs of the form [u, u]. A repeated pair is not a loop by itself, but a job that depends on itself is. Jobs may be unrelated to one another, so the graph can be disconnected.
The graph can be large; use an O(n + m) approach and avoid deep recursion.
Example 1
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3],[3,1]]
- Output:
- true
- Explanation:
Jobs 1, 2 and 3 wait on each other in a circle, so they can never start.
Example 2
- Input:
- n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]
- Output:
- false
- Explanation:
Job 3 has two dependencies, but nothing leads back to an earlier job, so there is no loop.
Constraints
1 ≤ n ≤ 100000
0 ≤ edges.length ≤ 200000
edges[i] = [u, v] with 0 ≤ u, v < n; pairs may repeat and u may equal 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 2,800 msC++ 700 msJava 1,400 msJavaScript 1,400 msTypeScript 1,400 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)