684. 冗余连接

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        /**
        并查集:
            找不到y，说明x与y不连通，可相连。找到y，说明x与y已连通，相连成环
         */
         //1 初始化
         int parent[] =new int[edges.length+1];
         for(int i=1;i<parent.length;i++){
             parent[i]=i;
         }
         for(int i=0;i<edges.length;i++){
             int [] edge=edges[i];
             int node1=edge[0];int node2=edge[1];
             if(find(parent,node1)!=find(parent,node2)){
                 union(parent,node1,node2);
             }else{
                 return edges[i];
             }

         }
         return new int[0];


    }

    //2查找
    public int find(int [] parent,int index){
      
        if(parent[index]!=index){
            parent[index]=find(parent,parent[index]);
        }
        return parent[index];
    }

    //3合并
    public void union(int [] parent,int index1,int index2){
        parent[find(parent,index1)]=find(parent,index2);//index1的父亲的父亲指向index2
    }
}