Leetcode 2204 Distance to a Cycle in Undirected Graph

Problem statement

https://leetcode.com/problems/distance-to-a-cycle-in-undirected-graph/

Solution

Find all nodes with degree 1: our leafs and cut them from tree. Always continue to cut nodes with indegree 1 if possible. What is left in the end is our loop.
Start multi-source bfs from nodes in loop.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def distanceToCycle(self, n, E):
        deg, G = [-1] * n, defaultdict(list)
        for x, y in E:
            G[x] += [y]
            G[y] += [x]
            deg[x] += 1
            deg[y] += 1

        S = [x for x in range(n) if deg[x] == 0]
        while S:
            x = S.pop()
            for y in G[x]:
                if not deg[y]: continue
                deg[y] -= 1
                if deg[y] == 0: S += [y]

        Q = deque([(0, x) for x in range(n) if deg[x]])
        dist = [-1] * n
        for _, x in Q: dist[x] = 0

        while Q:
            d, x = Q.popleft()
            dist[x] = d
            for y in G[x]:
                if dist[y] != -1: continue
                Q.append((d + 1, y))

        return dist