题目描述

在这个问题中，树是一个连接的无向图，没有环。

给定输入是以具有N个节点（具有不同值1,2，…，N）的树开始的图，其中添加了一个附加边。添加的边有两个不同的顶点，从1到N中选择，并且不是已经存在的边。

得到的图形作为2D边缘阵列给出。边的每个元素是一对[u，v]，其中u <v，表示连接节点u和v的无向边。

返回可以删除的边，以便生成的图是N个节点的树。如果有多个答案，则返回给定2D阵列中最后出现的答案。答案边[u，v]应采用相同的格式，u <v。

样例

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
说明: 给出的例子的图长这样，加上了[1,4]边以后就出现了1-2-3-4的环，所以1-4边是冗余的，所以是答案
5 - 1 - 2
    |   |
    4 - 3

算法

(并查集) $O(n)$

出现环的条件是某条边，边的两个端点原本就是连通的，那么加上了这条边以后就产生了环，因此我们在加入每条边的时候需要判断一下边的两个端点本身是不是连通的即可。

时间复杂度分析：需要遍历一遍输入的边，对每条边的两个端点进行一下合并操作，合并的复杂度是常数的，所以最后复杂度为$O(n)$。

C++ 代码

class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    bool Union(int a, int b){//返回a和b是否本身在一个集合里
        int fa = Find(a);
        int fb = Find(b);
        bool res = fa==fb;
        father[fb] = fa;
        return res;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        UnionFind UF(N+1);
        vector<int>res(2, 0);
        for(int i = 0; i < edges.size(); i++){
            int u = edges[i][0];
            int v = edges[i][1];
            if(UF.Union(u, v)){//冗余
                res[0] = u;
                res[1] = v;
            }
        }
        return res;
    }
};