Leetcode-684.冗余连接

题目描述
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

运行结果

解题思路
原题是在树的基础上加上了一个边。所以我们需要遍历给出的边，如果出现了环，则应去除，否则不用
利用并查集：刚开始属于不同的连通集，如果存在边，则归入一个连通集。否则则出现环
题意是返回列表中最后一个：但是按题意最多只有一个环，而我们找到的已经是环的最后一条边。所以不需要特殊处理
java代码

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n=edges.length;
        int[] parent=new int[n+1];
        for(int i=1;i<n+1;i++){
            parent[i]=i;
        }
        for(int i=0;i<n;i++){
            int[] edge=edges[i];
            int node1=edge[0];
            int node2=edge[1];
            if(find(parent,node1) != find(parent,node2)){
                parent[find(parent,node1)]=find(parent,node2);
            }
            else{
                return edge;
            }
        }
        return new int[0];
    }
    public int find(int[] parent,int index){
        if(parent[index]== index){
            return index;
        }
        else{
            return find(parent,parent[index]);
        }
    }
}