代码随想录算法训练营第六十二天 | 108. 冗余连接、109. 冗余连接II、复习

108. 冗余连接

题目链接：https://kamacoder.com/problempage.php?pid=1181
文档讲解：https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF…

思路

从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。然后直接输出。

代码

import java.util.*;

class Main {
    static int[] father;
    static int n;
    
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        father = new int[n + 1];
        init();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            if (isSame(a, b)) {
                System.out.println(a + " " + b);
                return;
            } else {
                join(a, b);
            }
        }
    }
    
    public static void init() {
        for (int i = 1; i <= n; i++) father[i] = i;
    }
    
    public static int find (int u) {
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    
    public static boolean isSame(int u, int v) {
        return find(u) == find(v);
    }
    
    public static void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
}

109. 冗余连接II

题目链接：https://kamacoder.com/problempage.php?pid=1182
文档讲解：https://www.programmercarl.com/kamacoder/0109.%E5%86%97%E4%BD%99%E8%BF…

思路

有向树的性质，如果是有向树的话，只有根节点入度为0，其他节点入度都为1。

情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
情况二：入度为2 还有一种情况，只能删特定的一条边。
情况三：如果没有入度为2的点，说明图中有环了。

用数组把每条边记录下来，并统计节点入度，如果存在入度为2的节点，则实现函数isTreeAfterRemoveEdge()，否则实现函数getRemoveEdge()。

isTreeAfterRemoveEdge()判断删一个边之后是不是有向树：将所有边的两端节点分别加入并查集，遇到要删除的边则跳过，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。如果顺利将所有边的两端节点（除了要删除的边）加入了并查集，则说明删除该条边是一个有向树。
getRemoveEdge()确定图中一定有了有向环，那么要找到需要删除的那条边：将所有边的两端节点分别加入并查集，如果遇到即将加入并查集的边的两端节点本来就在并查集了，说明构成了环。

代码

import java.util.*;
class Main {
    static int[] father, inDegree, vec;
    static int[][] edges;
    static int n;
    
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        inDegree = new int[n + 1];
        vec = new int[2]; // 保存edges中对应边的行数
        father = new int[n + 1];
        edges = new int[n][2];
        for (int i = 0; i < n; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            inDegree[edges[i][1]]++;
        }
        int j = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                vec[j++] = i;
            }
        }
        if (j > 0) {
            if (isTreeAfterRemoveEdge(vec[0])) {// 如果移掉这条边后是树，则输出
                System.out.println(edges[vec[0]][0] + " " + edges[vec[0]][1]);
            } else {
                System.out.println(edges[vec[1]][0] + " " + edges[vec[1]][1]);
            }
            return;
        }
        getRemoveEdge();
    }
    
    public static void init() {
        for (int i = 1; i <= n; i++) father[i] = i;
    }
    
    public static int find(int u) {
        return u == father[u] ? u : (father[u] = find(father[u]));
    }
    
    public static boolean isSame(int u, int v) {
        return find(u) == find(v);
    }
    
    public static void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        father[v] = u;
    }
    
    public static boolean isTreeAfterRemoveEdge(int index) {
        init();
        for (int i = 0; i < n; i++) {
            if (i == index) continue;
            if (isSame(edges[i][0], edges[i][1])) return false;
            else join(edges[i][0], edges[i][1]);
        }
        return true;
    }
    
    public static void getRemoveEdge() {
        init();
        for (int i = 0; i < n; i++) {
            if (isSame(edges[i][0], edges[i][1])) {
                System.out.println(edges[i][0] + " " + edges[i][1]);
                return;
            } else join(edges[i][0], edges[i][1]);
        }
    }
}