LeetCode-冗余连接-题解[并查集]

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」

题目要求

题目描述

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

示例

示例 1

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
复制代码

示例 2

输入: 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 中无重复元素
• 给定的图是连通的 

解题思路

简单的并查集，我们可以假设初始时所有的节点的父节点都是自己，之后对所有的边进行遍历。对每条边两个节点间的关系进行判断。若在加入该边前，两个节点属于不同的连通分量，则说明加上该边前，该两点之间不连通，加上该边不会导致环出现，我们将这两个节点加入同一个连通分量。若在加入该边前，两个节点属于同一连通分量，则加上该边会导致环的出现，记录下该边。在遍历完所有边之后，即可得出使树成为环的最后一条边。

代码

class Solution {
public:
    int fa[1010] = {0};
    vector<int> res;
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for(int i = 0; i<edges.size(); i++) fa[i] = i;
        res.push_back(0);res.push_back(0);

        for(int i=0; i<edges.size(); i++){
            merge(edges[i][0], edges[i][1]);
        }
        return res;
    }
     int find(int k){
        //  if(k == fa[k]){
        //      return k;
        //  }else{
        //      fa[k] = find(fa[k]);
        //      return fa[k];
        //  }
         return k == fa[k] ? k : (fa[k] = find(fa[k]));
     }
     void merge(int m, int n){
         int a = find(m);
         int b = find(n);
         fa[b] = a;
         if(a==b){
             res[0] = m;
             res[1] = n;
         }
     }
};
复制代码