【个人笔记】685. 冗余连接 II 的解释（并查集）

一棵树有n个点和n条边，返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。
解释：
注意不冗余的有根树的特性！**根节点入度为0，其余结点只有一个入度！**所以冗余的两种情况如下：
（1）有一个结点有2个入度（破环其他结点只有一个入度的条件）（可能成环可能不成环）
（2）形成一个每个节点都只有一个入度的环（破环根节点入度为0的条件）（成环）

对于情况（1），找到入度为2的结点（只关注入度值）然后返回冗余的边就行了，但是：
1）当不成环时，返回任意一条都行
在这里插入图片描述
2）当成环时，要返回构成环的那条

所以这里只处理不成环的情况，入度为2时的边记为conflict，并跳过这种可能会导致冗余的边（无论是情况1)的真冗余边还是2)的非冗余边）。把成环的情况合并成到（2）解决。
（所以这里的情况2)出现时，可能造成冗余的边将被跳过）
（a）没去掉真正的冗余边，会出现情况（2）成环
在这里插入图片描述
或者(b)去掉了真正的冗余边，不会出现情况（2）

对（2），入度不为2的结点需要判定是否成环。如果该结点入度不为2，且属于同一个并查集，说明成环
记录形成有向环的那条边为circle，最后删掉构成环的边就可以了。

由于肯定存在一条冗余边，如果只有circle，那就是circle，如果只有conflict，那就是conflict，如果两个都有，说明是（1）的成环的情况（a）
但是！可能得到circle时是这样！构成环的临门一脚不一定就是要删的那个，左边那个才是真正要删的！
在这里插入图片描述
所以需要用一个祖先数组ancestors记录“上一个结点”，要找到这个冗余边，就是找指向edges[conflict][1]的上一个结点
因为只有入度不为2才会更新ancestors，所以ancestors记录的边必然排除了conflict记录的那条。有了ancestors，也不用存入度了，直接：如果ancestors[v]!=v，说明有其他父节点（入度为2）
即：冗余边为
（ancestors[edges[conflict][1]], edges[conflict][1]）

class UnionFind{
    int[] parents;

    UnionFind(int l){
        parents = new int[l];
        Arrays.fill(parents, -1);
    }

    int find(int x){
        if (parents[x] < 0) {
            return x; // 如果是根节点，则返回
        }
        // 路径压缩
        return parents[x] = find(parents[x]);
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (parents[rootX] < parents[rootY]) {  // 负数 <说明rootY下标的结点数更少
                parents[rootX] += parents[rootY];
                parents[rootY] = rootX;  // 小树合并到大树
            }else{
                parents[rootY] += parents[rootX];
                parents[rootX] = rootY;  // 小树合并到大树
            }  // 否则parent[rootX] = parent[rootY]，不管
        }
    }
}

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int conflict = -1;  // 冲突（俩父节点）
        int cycle = -1;     // 环

        int[] parent = new int[edges.length];
        for(int i=0; i<edges.length; i++){
            parent[i] = i;   // 要记录指向环路那个！！
        }

        UnionFind uf = new UnionFind(edges.length);
        for(int i=0; i<edges.length; i++){
            int u = edges[i][0]-1, v = edges[i][1]-1;
            if(parent[v]!=v){  // 入度为2
                conflict = i;   // 冲突，v有俩父结点不同的路径
            }else{  // 判断是否成环
                if(uf.find(u)==uf.find(v)){  // 成环
                    cycle = i;
                }else{  // 正常
                	parent[v] = u;  // u是v的父节点
                    uf.union(u, v);
                }
            }
        }
        if(conflict==-1){   // 只存在环路
            return edges[cycle];
        }
        if(cycle==-1){  // 只存在冲突
            return edges[conflict];
        }
        // 都有，则附加的边不可能是 [u,v]
        //（因为[u,v] 已经被记为导致冲突的边，不可能被记为导致环路出现的边），
        // 因此附加的边是 [parent[v],v]。
        int[] res = {parent[edges[conflict][1]-1]+1, edges[conflict][1]};
        return res;
    }
}