141、★并查集-LeetCode-冗余连接Ⅰ和Ⅱ

题目：

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

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/redundant-connection

 

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/redundant-connection-ii

思路：

在一棵树中，边的数量比节点的数量少1！n个节点，就有n-1条边

①冗余连接Ⅰ

1）并查集：用在图论中，无向图！

拥有多个功能：感觉合并时的顺序从始至终保持一致，需要题目给出的情况也有顺序要求！

1.初始化(就是给未连接时的各个节点分配根节点，也叫作代表节点)，说明了节点属于哪个集合！

2.查看根节点：也就是找属于哪个节点

3.合并节点：就是将两个合并为同一个集合，表示已经连接过

遇到属于同一个集合的两个节点时，直接返回就是结果；

②冗余连接Ⅱ：有根树？只有一个根节点，除了根节点，其他节点都有且只有一个父节点，根节点没有父节点

只有一个入度为0的节点，为根节点；不存在入度为2的节点；除了根节点，其他节点入度为1

1）思路：

①有根树加入一条边，一定会引入一个环！

②并且可能会引入冲突(有根树中不存在入度为2的节点，出现这种节点就是出现了冲突)；

所以加入一条新边后会出现三种情况：1. 只出现了环；2.出现了冲突，冲突的边都在环中；3.出现冲突，只有一条边在环中！

解决方式：1.环只需要使用并查集判断即可；2.删除一条边，即可实现区冲突加去环；3.只有删除环中的冲突边才能既去环又去冲突。

怎么判断第3种情况呢？

判断删除边后，图中是否还有环即可；还有环就删除另一个冲突边

整体的判断方法：最重要的就是并查集判断环，删除边；还有就是判断冲突节点！

代码：

1）并查集：时间复杂度O(NlogN)

有个问题：如果测试用例中[1,2]、[1,3]，[2,3|]换成了[1,2]、[3,1]，[2,3]是不是就出错了！

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int len = edges.length;
        int[] parent = new int[len + 1];//根节点列表，代表的是每个节点的根节点，也就是属于哪个集合
        //并查集初始化：初始时，各自属于自己的集合
        for(int i = 1;i <= len;i++){
            parent[i] = i;//简单的情况：下标对应数字
        }
 
        for(int i = 0;i < len;i++){
            int[] edge = edges[i];//是一个长度为2的数组
            int nums1 = edge[0],nums2 = edge[1];//一个边上的两个节点
            if(find(parent,nums1) != find(parent,nums2)){
                //两个节点属于不同的集合，可以加一条边；更改根节点
                union(parent,nums1,nums2);
            }else{
                return edge;
            }
        }
        return new int[0];
 
    }
    //并查集：合并(也就是放到一个集合中，拥有同一个根节点)
    public void union(int[] parent,int index1,int index2){
        //连接节点的操作，也就是将节点添加到同一个集合中
        //通过使其拥有相同的根节点来表现
        //方式1：parent[find(parent,index1)] = find(parent,index2);
        //方式2：
        int n1 = find(parent,index1);
        int n2 = find(parent,index2);
        parent[n1] = n2;
    }
 
    //查找根节点(根节点是用来判断是不是在同一个集合中)；找到了根节点，就可以判断
    public int find(int[] parent,int index){
        if(parent[index] != index){//下标数字与具体数值对应？
            parent[index] = find(parent,parent[index]);//递归查找
        }
        return parent[index];
    }
}

2）冗余连接Ⅱ：

class Solution {
    int parent[];// 记录节点的根节点，类似上一道题划分集合
    public int[] findRedundantDirectedConnection(int[][] edges) {
        //初始化：
        parent = new int[1001];//并查集
        int[] in = new int[1001];//辅助找入度为2的节点
        int[] res = new int[]{};
 
        //①寻找是否存在入度为2的节点
        for(int[] edge : edges){
            //指向它两次，就是入度为2
            if(++in[edge[1]] == 2){//判断出现了几次
                res = edge;
            }
        }
        //如果找到了，res就是一个长度为2的数组
        if(res.length != 0){
            if(check(edges,res)) return res;
            else{//冲突边有两个：
                for(int[] e : edges){
                    if(e[1] == res[1]){
                        if(check(edges,e)) return e;
                    }
                }
            }
        }
         // 不存在入度为2的节点：按照无向图，判断即可
         //初始化
        for (int i = 0; i <= 1000; i++) {
            parent[i] = i;
        }
        for (int[] e : edges) {
            // 删除加入形成环的边
            if (find(parent,e[0]) == find(parent,e[1])) return e;
            else union(parent,e[0], e[1]);
        }
        return new int[0];
    }
    
    // 判断有向边构成的图形是否为树
    boolean check(int[][] edges, int[] remove) {
        // 初始化并查集
        for (int i = 0; i <= 1000; i++) {
            parent[i] = i;
        }
        for (int[] e : edges) {
            if (Arrays.equals(e, remove)) continue;//直接不比较，不加并查集，就说明删除了该边
            // 删除之后构成的图案不为树
            if (find(parent,e[0]) == find(parent,e[1])) return false;
            else union(parent,e[0], e[1]);
        }
        return true;
    }
    
    //并查集中找根节点
    public int find(int[] parent,int index){
        if(parent[index] != index){
            //如果x对应的不是自己，说明划分了集合！
            //找到了划分的新的结合节点后，要判断现在这个还有没有更上一层的父节点
            parent[index] = find(parent,parent[index]);
        }
        return parent[index];
    }
    //合并
    public void union(int[] parent,int index1,int index2){
        if(find(parent,index1) != find(parent,index2)){//肯定是初始状态
            parent[find(parent,index2)] = parent[index1];
        }
    }
 
}
代码改自LeetCode-阿尼亚