Problem statement

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

Solution

Actually, what we need to do in this problem is to find loop. We can do it, using dfs or we can use Union Find idea. Let us add edges one by one and when we see that we have a loop, that is two ends of our connection were already in the same component, we return it immedietly. Note, that because nodes enumerated from 1, not 0, we need to deal with this as well.

Complexity

In this problem we have tree with one edge added, so there will be both n nodes and edges. So, if we assume that operations for our union find structure can be done in O(1), total complexity will be O(n). (In fact in my code I use dsu without ranks and with paths compression for simplicity, but due to small tests it works almost the same, in theory it is O(log n) complexity). Space complexity is O(n) as well.

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def findRedundantConnection(self, edges):
        N = len(set(chain(*edges)))
        dsu = DSU(N)
        for i, j in edges:
            if dsu.find(i-1) == dsu.find(j-1):
                return([i,j])
            else:
                dsu.union(i-1,j-1)