688. Undirected Loop Check
A village has n houses numbered 0 to n - 1 and a list edges of two-way footpaths, where [u, v] joins house u and house v. A walker wants to know whether the paths contain a loop: a way to leave a house, walk along distinct footpaths and return to the starting house.
Return true if such a loop exists and false otherwise. A footpath from a house to itself counts as a loop, and so do two separate footpaths listed between the same pair of houses. Houses may be disconnected from each other.
Solve it in near-linear time, for example with a disjoint-set structure.
Example 1
- Input:
- n = 5, edges = [[0,1],[1,2],[3,4]]
- Output:
- false
- Explanation:
The footpaths form two separate chains, so there is no way to return to a starting house.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3],[3,1]]
- Output:
- true
- Explanation:
Houses 1, 2 and 3 are joined in a ring, so a walker can return to where they began.
Example 3
- Input:
- n = 2, edges = [[0,1],[1,0]]
- Output:
- true
- Explanation:
Two separate footpaths join the same pair of houses, which counts as a loop.
Constraints
1 ≤ n ≤ 100000
0 ≤ edges.length ≤ 100000
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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(m * alpha(n))
- Space
- O(n)