今日题目

https://leetcode.com/problems/redundant-connection/description/

解题思路

注意在环中，每个节点的度数都大于 1。因此，如果我们不断删除度数为 1 的节点，最终剩余的节点就构成了一个环。

解题方法

注意节点编号从 1 到 n，处理时需要将索引减一进行对齐。

复杂度

  • 时间复杂度：$O(N)$

  • 空间复杂度：$O(N)$

代码

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        N = len(edges)
        du = [0] * (N)
        E = [[] for _ in range(N)]
        for x,y in edges:

            x -= 1
            y -= 1

            du[x] += 1
            du[y] += 1

            E[x].append(y)
            E[y].append(x)
        q = deque([])
        for i in range(N):
            if du[i] == 1:
                q.append(i)

        # print(du)

        while(len(q) > 0):
            x = q.popleft()
            du[x] = 0
            for to in E[x]:
                if du[to] > 0:
                    du[to] -= 1
                if du[to] == 1:
                    q.append(to)
        
        # print(du)

        loop = set([])
        for i in range(N):
            if du[i] > 0:
                loop.add(i)
        
        for i in range(N - 1, -1, -1):
            x,y = edges[i]
            if x - 1 in loop and y - 1 in loop:
                return [x, y]
        
        return None