Does a Directed Graph Have a Cycle?
You are given a directed graph with n vertices numbered 0 to n - 1, and a list edges. Each edge [u, v] goes from u to v, and you can move along it only in that direction.
A cycle is a path that follows the edge directions and comes back to the vertex where it started.
Return true if the graph has at least one cycle, and false if it has none.
Note
- The graph may have several separate parts. Check every part.
- An edge from a vertex to itself (
[u, u]) is allowed, and it is a cycle by itself. - The same edge
[u, v]never appears twice. Both[u, v]and[v, u]may appear, and together they make a cycle. - Reaching a vertex a second time by a different path is not a cycle. A cycle must return to its start.
Hint: count how many edges point into each vertex. Repeatedly remove a vertex that has no edge pointing into it. If you cannot remove every vertex this way, the vertices that are left are part of a cycle or lead into one.
Examples
Example 1
- Input:
- 5, [[0,1],[1,2],[2,3],[3,1],[4,0]]
- Output:
- true
Following the edges 1 → 2 → 3 → 1 comes back to vertex 1, so there is a cycle.
Example 2
- Input:
- 4, [[0,1],[0,2],[1,3],[2,3]]
- Output:
- false
Vertex 3 can be reached in two ways, from 1 and from 2. But no path leaves vertex 3, so no path returns to where it started.
Example 3
- Input:
- 3, [[0,1],[2,2]]
- Output:
- true
The edge [2, 2] goes from vertex 2 back to itself. That is a cycle.
Constraints
1 <= n <= 150 <= edges.length <= 40edges[i] = [u, v]with0 <= u, v < n- No edge
[u, v]appears more than once.
Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.