LeetCode 684. 冗余连接

题目

树可以看成是一个连通且无环的无向图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

例：
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

方法：并查集

• n 记录边的数量，因为此时是一个树加一条边导致形成了一个有环的无向图，所以同时也是点的数量
• parent 记录每个节点所在集合的代表节点，初始设置各个节点自己为一个集合，那么每个节点的代表节点为其自己
• 遍历边集合，node1 表示边左边的点，node2 表示边右边的点
  • 若两个点的集合的代表节点不同，那么表示两个点不在同一集合，两个点并不相连，将两个点所在集合合并为同一集合，此时两个点可以相连
  • 若两个点的集合的代表节点相同，那么表示两个点在同一集合，两个点可以通过某种路径相连，将此时的边加入的话，就会生成环，所以该边即为导致有环的原因，返回该边

find 函数：寻找节点所在集合的代表节点

• 若此节点所在集合的代表节点不为其自身，则需通过调用 find 函数继续寻找其代表节点
• 最终返回该节点的代表节点

union 函数：将两个节点的集合合并，两个集合拥有同一代表节点

• 将第二个节点的代表节点设置为第一个节点的代表节点

class Solution(object):
    def findRedundantConnection(self, edges):
        n = len(edges)
        parent = [i for i in range(n+1)]

        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1, index2):
            parent[find(index1)] = find(index2)
        
        for node1, node2 in edges:
            if find(node1) != find(node2):
                union(node1, node2)
            else:
                return [node1, node2]

        return []

相关知识

• 并查集：
  集合树： 所有节点以代表节点为父节点构成的多叉树
  节点的代表节点： 可以理解为节点的父节点，从当前节点出发，可以向上找到的第一个节点
  集合的代表节点： 可以理解为根节点，意味着该集合内所有节点向上走，最终都能到达的节点

参考

代码相关：https://leetcode.cn/problems/redundant-connection/solution/rong-yu-lian-jie-by-leetcode-solution-pks2/
并查集：https://leetcode.cn/problems/redundant-connection/solution/tong-su-jiang-jie-bing-cha-ji-bang-zhu-xiao-bai-ku/