leetcode-684：冗余连接

题目

题目连接

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

给定往一棵 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]

解题

方法一：并查集

遍历edge，如果发现已经连同的，那么更新res。
最后得到的res，一定是最后出现的并且已连通的。

class UnionFind{
    
private:
    vector<int> parent;
public:
    UnionFind(int n){
    
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        return parent[index]=find(parent[index]);
    }
    bool unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1==p2) return false;//如果已经连通，那么返回false
        else{
    
            parent[p1]=p2;
            return true;
        }
        
    }
};
class Solution {
    
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    
        vector<int> res;
        int n=edges.size();
        UnionFind uf(n+1);
        for(vector<int>& edge:edges){
    
            if(!uf.unite(edge[0],edge[1])) res=edge;
        }
        return res;
    }
};