684. 冗余连接

水深无声 2022-10-08 05:48 124阅读 0赞

> 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
> 
> 结果图是一个以边组成的二维数组。每一个边的元素是一对\[u, v\] ，满足 u < v，表示连接顶点u 和v的无向图的边。
> 
> 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 \[u, v\] 应满足相同的格式 u < v。
> 
> 示例 1：
> 
> 输入: \[\[1,2\], \[1,3\], \[2,3\]\]  
> 输出: \[2,3\]  
> 解释: 给定的无向图为:  
>   1  
>  / \\  
> 2 - 3  
> 示例 2：
> 
> 输入: \[\[1,2\], \[2,3\], \[3,4\], \[1,4\], \[1,5\]\]  
> 输出: \[1,4\]  
> 解释: 给定的无向图为:  
> 5 - 1 - 2  
>     |   |  
>     4 - 3

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
        }
    }