HardNo. 2204LeetCode Premium
Distance to a Cycle in Undirected Graph — LeetCode 2204 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Graph
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a positive integer n representing the number of nodes in a connected undirected graph containing exactly one cycle. The nodes are numbered from 0 to n - 1 (inclusive).
Example
- Input
- n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]
- Output
- [1,0,0,0,0,1,2]
- Explanation
- The nodes 1, 2, 3, and 4 form the cycle.
Python solution
class Solution:
def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:
g = defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
q = deque(i for i in range(n) if len(g[i]) == 1)
f = [0] * n
seq = []
while q:
i = q.popleft()
seq.append(i)
for j in g[i]:
g[j].remove(i)
f[i] = j
if len(g[j]) == 1:
q.append(j)
g[i].clear()
ans = [0] * n
for i in seq[::-1]:
ans[i] = ans[f[i]] + 1
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2204. Distance to a Cycle in Undirected Graph is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
Frequently asked questions
- How hard is LeetCode 2204. Distance to a Cycle in Undirected Graph?
LeetCode 2204. Distance to a Cycle in Undirected Graph is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2204. Distance to a Cycle in Undirected Graph?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2204. Distance to a Cycle in Undirected Graph?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2204. Distance to a Cycle in Undirected Graph cover?
LeetCode 2204. Distance to a Cycle in Undirected Graph is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.
- Is LeetCode 2204. Distance to a Cycle in Undirected Graph a premium problem?
Yes. LeetCode 2204. Distance to a Cycle in Undirected Graph is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.