685. 冗余连接 II

原题链接：

685. 冗余连接 II

https://leetcode.cn/problems/redundant-connection-ii/description/

完成情况：

解题思路：

这段代码实现了一个解决有向图中存在冗余连接的问题的算法。下面是对代码的清晰、简洁和可读性强的解释：

1. UnionFind 类定义了一个并查集数据结构，用于处理节点之间的连接关系。

   • ancestor 数组用于记录每个节点的祖先节点。

2. findRedundantDirectedConnection 方法是解决问题的核心部分。

   • 首先初始化一些变量和数据结构，包括并查集 uf、节点父节点数组 parent 等。
   • 遍历图中的每条边，对每条边进行处理。
   • 如果发现当前边的终点节点已经有父节点（即 parent[node2] != node2），则表示存在冲突，记录下当前边的下标为 conflict。
   • 否则，将当前边加入并查集中，并判断是否形成了环，如果形成了环，则记录下当前边的下标为 cycle。
   • 最后根据是否存在冲突来返回结果，如果存在冲突则返回冲突边，否则返回形成环的边或者最后一条边。

3. UnionFind 类中的 union 方法和 find 方法分别用于合并节点和查找节点的祖先。

总体来说，这段代码通过并查集的方式处理了有向图中存在冗余连接的问题，其中涉及到了判断冲突、检测环和返回结果等步骤。

参考代码：

package 代码随想录.并查集;

import java.util.ArrayList;

public class _685冗余连接II {
    int N_node = 1002;
    int fatherPaths [] ;

    public _685冗余连接II() {
        fatherPaths = new int[N_node];
        //并查集初始化
        for (int i = 0; i < N_node; i++){
            fatherPaths[i] =  i;
        }
    }

    /**
     * 有向图形成输，然后去除掉节点，存在多个 节点则删除掉最后一个节点
     * @param edges
     * @return
     */
    public int[] findRedundantDirectedConnection(int[][] edges) {
        //这次主要是多了一个方向，构造父亲节点，寻根的时候要考虑方向问题
        int [] inDegree = new int[N_node];  //记录入度边
        for (int i = 0;i< edges.length;i++){
            //入度边
            inDegree[edges[i][1]] += 1;
        }
        //找出入度为 2的节点所对应的边，注意要倒序，因为优先返回最后出现在二维数组中的答案
        ArrayList<Integer> twoInDegree = new ArrayList<Integer>();  //注意要重点留意那些有多个入度的边，因为如果只有一个节点的话，你删除掉了那个节点，那么就会导致出现单节点，就无法构成一颗树
        for (int i = edges.length - 1;i>=0;i--){
            if (inDegree[edges[i][1]] == 2){    //只要大于1条边就记录下来
                twoInDegree.add(i);
            }
        }

        //处理图中情况1 和情况2
        //明确没有入度大于2的情况了，那么一定有有向环，找到构成环的边返回就可以了
        if (!twoInDegree.isEmpty()){
            if (isTreeAfterRemoveEdge(edges,twoInDegree.get(0))){
                return edges[twoInDegree.get(0)];
            }
            return edges[twoInDegree.get(1)];
        }

        //明确没有入度为2的情况，那么 一定有有向环，找到构成环的边返回就可以了
        return getRemoveEdge(edges);
    }

    /**
     * 在有向图里找到删除的那条边，使其变成树
     * @param edges
     * @return 要删除的边
     */
    private int[] getRemoveEdge(int[][] edges) {
        initFatherPath();
        for (int i = 0; i < edges.length; i++) {
            if (sameEdge(edges[i][0], edges[i][1])){    //构成 有向环了，就删除要删除的边
                return edges[i];
            }
            joinEdge(edges[i][0],edges[i][1]);
        }
        return null;
    }

    /**
     * 并查集里寻根的过程
     */
    private int findRoot(int node){
        if (node  == fatherPaths[node]){
            return node;
        }
        fatherPaths[node] = findRoot(fatherPaths[node]);
        return fatherPaths[node];
    }

    /**
     *
     * @param edgeA
     * @param edgeB
     */
    private void joinEdge(int edgeA, int edgeB) {
        edgeA = fatherPaths[edgeA];
        edgeB = fatherPaths[edgeB];
        if (edgeA == edgeB) return;
        fatherPaths[edgeB] = edgeA; //     A -> B
    }

    /**
     *
     * @param edgeA
     * @param edgeB
     * @return
     */
    private boolean sameEdge(int edgeA, int edgeB) {
        edgeA = fatherPaths[edgeA];
        edgeB = fatherPaths[edgeB];
        return edgeB == edgeA;
    }

    /**
     *
     */
    private void initFatherPath() {
        //并查集初始化
        for (int i =0;i<N_node;++i){
            fatherPaths[i] = i;
        }
    }

    /**
     * 删一条边之后判断是不是树
     * @param edges
     * @param deleteEdge 要删除的边
     * @return  true: 是树， false： 不是树
     */
    private boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge) {
        initFatherPath();
        for (int i = 0; i < edges.length;i++){
            if (i == deleteEdge)    continue;
            if (sameEdge(edges[i][0],edges[i][1])){ //构成有向环了，一定不是树
                return false;
            }
            joinEdge(edges[i][0],edges[i][1]);
        }
        return true;
    }
}

错误经验吸取