684 冗余连接（无向图中找环-并查集）

小灰灰 2022-09-03 00:28 129阅读 0赞

**1. 问题描述：**

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

**示例 1：**

![20210804182331725.png][]

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

**示例 2：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

输入: edges = \[\[1,2\], \[2,3\], \[3,4\], \[1,4\], \[1,5\]\]  
输出: \[1,4\]

**提示:**

n == edges.length  
3 <= n <= 1000  
edges\[i\].length == 2  
1 <= ai < bi <= edges.length  
ai != bi  
edges 中无重复元素  
给定的图是连通的  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/redundant-connection

**2. 思路分析：**

分析题目可以知道本质上在一个**无向图中找一个环**，在无向图找环最简单的方法是**并查集**，我们每一次可以合并一条边对应的两个顶点，如果这两个顶点不在同一个集合中（也即他们的父节点是不同的）那么可以直接合并，如果两个顶点已经在同一个集合中了说明加入当前的边之后肯定就会形成环，返回当前的这条边即可，我们可以从前往后枚举每一边，在遍历边的时候合并边的两个顶点在同一个集合中，若发现当前这两个顶点已经在同一个集合中了那么直接返回当前这条边即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        #  并查集的查询操作: 寻找x的父节点, 在查询的时候合并父节点
        def find(self, p: List[int], x: int):
            if x != p[x]: p[x] = self.find(p, p[x])
            # 注意返回的是p[x]
            return p[x]
    
        def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
            # 边和点的数目都是n
            n = len(edges)
            # 下标从1开始那么需要多声明一个长度
            p = [0] * (n + 1)
            # 初始化并查集的父节点
            for i in range(1, n + 1):
                p[i] = i
            # 从前往后枚举每一条边, 当发现当前的两个顶点在同一个集合中那么返回当前的边即可
            for e in edges:
                a, b = self.find(p, e[0]), self.find(p, e[1])
                if a != b:
                    p[a] = b
                else:
                    return e
            return list()

[20210804182331725.png]: /images/20220829/d67105cba4d64ad1a574cc8a54f2b9e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/dd17b408dcb44bafaa56a01435d827db.png