Interview problem: Union Find

 Leetcode 684

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))
        rank = [0] * (n + 1)
        def _find(x):
            if parent[x] == x:
                return x
            parent[x] = _find(parent[x])
            return parent[x]
        def _union(x, y):
            x = _find(x)
            y = _find(y)
            if rank[x] > rank[y]:
                x, y = y, x
            if rank[x] == rank[y]:
                rank[y] += 1
            parent[x] = y
            return y
        for x, y in edges:
            if _find(x) == _find(y):
                return [x, y]
            _union(x, y)