冗余连接-并查集684-python

并查集问题，在find和union函数中找出问题的解决办法。

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = [0] * n # 祖先数组：用于记录每一个节点的祖先
        res = []

        # 祖先数组初始化
        def init(n):
            for i in range(n):
                parent[i] = i+1
        
        init(n)

        # 查找节点祖先
        def find(i):
            if i == parent[i-1]:
                return i
            else:
                parent[i-1] = find(parent[i-1])
            
            return parent[i-1]    
        
        #　连通
        def union(i, j):
            par_i = find(i)
            par_j = find(j)
            
            if par_i == par_j: # 如果之前已经连通了，则为多余的边
                #　题意表示有多个边时删除最后一个出现的边
                #  所以先把待删除的边做记录
                res.append([i, j])
            else:
                parent[par_i-1] = par_j
        
        for edge in edges:
            union(edge[0], edge[1])
        
        return res[-1]