Detect Cycle in an Undirected Graph
MediumP2Coding
An undirected graph has n vertices labelled 0..n - 1 and a list of edges, each [u, v]. The graph may be disconnected. There are no self-loops and no repeated edges. Return true if the graph contains a cycle.
Example 1
- Input
- n = 5, edges = [[0,1],[1,2],[2,3],[3,1]]
- Output
- true
- Why
- 1 - 2 - 3 - 1 is a cycle.
Example 2
- Input
- n = 4, edges = [[0,1],[1,2],[2,3]]
- Output
- false
Constraints
- 1 <= n <= 10^4
- 0 <= edges.length <= 5 * 10^4
- 0 <= u, v < n, u != v, no duplicate edges
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.