684_冗余连接.org

题目

思路

并查集

明确概念：

1.集合树：所有节点以代表节点为父节点构成的多叉树

2.节点的代表节点：可以理解为节点的父节点，从当前节点出发，可以向上找到的第一个节点

3.集合的代表节点：可以理解为根节点，意味着该集合内所有节点向上走，最终都能到达的节点

具体解析：

1.初识时，1-N每一个结点独自构成一个集合，每一个结点所在集合的「代表结点」就是该结点自身

2.引入一条边[a, b]时，统一视为a -> b，即a指向b，可以视b是a的父结点；分别计算a、b结点各自所在集合的代表结点a’，b’

3.如果 a’==b’。说明加入边[a, b]后肯定形成了闭环，直接返回[a, b]；否则更新 nums[a’] = b’；继续遍历下一条边。

add-lyf:易错 由于问题中可能存在不同子图之间的关系，故不能直接通过边的数量和顶点数量来判断是否有环！

code

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        def find(nums, val):
            # 查找 val 所在集合的「代表节点」
            while val != nums[val]:    
                val = nums[val]
            return val
                    
        n = len(edges)
        # 并查集初始化
        nums = [i for i in range(n + 1)]
        for e in edges:
            e1, e2 = e
            # 两个结点都需要去查找自己所在集合的代表节点!
            e1 = find(nums, e1)
            e2 = find(nums, e2)
            if e1 == e2: # 集合的代表结点出现重复，肯定存在环
                return e
            nums[e1] = e2
        return []

        # reference：https://leetcode-cn.com/problems/redundant-connection/solution/tong-su-jiang-jie-bing-cha-ji-bang-zhu-xiao-bai-ku/