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.

Distance to a Cycle in Undirected Graph — LeetCode 2204 Python Solution

HardLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #2204
Pattern: Union-Find
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

Python

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 ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

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.

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.