Today’s problem

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

Intuition

Note that in a ring, every node have more than one index. Therefore, if we delete all the index that has one index, the remaining points will be a ring.

Approach

Note that the label starts from 1 and ends at n, you would like to decrease index by one.

Complexity

  • Time complexity: $O(N)$

  • Space complexity: $O(N)$

Code

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