Day56--图论--108. 冗余的边（卡码网），109. 冗余的边II（卡码网）

方法：并查集

思路：

使用并查集，将每个边的from to都加到集合里面。

如果发现from to已经在集合里了，就说明他们在同一颗树上。

如果再把他们连起来，就会成环。所以这是要删除的边

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();Disjoint dj = new Disjoint(n);while (n-- > 0) {int from = in.nextInt();int to = in.nextInt();// 如果发现from to已经在集合里了，就说明他们在同一颗树上// 如果再把他们连起来，就会变成图。所以这是要删除的边if (dj.isSame(from, to)) {System.out.println(from + " " + to);return;} else {// 每个from to都加到集合里面dj.join(from, to);}}}
}class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public int find(int a) {if (a == father[a]) {return a;} else {return father[a] = find(father[a]);}}public boolean isSame(int o1, int o2) {return find(o1) == find(o2);}public void join(int o1, int o2) {int root1 = find(o1);int root2 = find(o2);if (root1 == root2) {return;}father[o2] = o1;}
}

方法：并查集

思路：

两个方向

1. 图中有一个入度为2的点
   • 情况一：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
   • 情况二，入度为2的点，只能删特定的一条边，因为有可能一删就不成树了，有孤点。
   • 综上，鉴于情况二，我们要模拟删除，看看它删后是否还构成树；鉴于情况一，如果都能删，题目要求要优先删除后面的。
   • 实际代码怎么做？
     • 倒序遍历入度为2的边，模拟删除后，是否还能构成树，能的话删。不能的话，删第二条边。
2. 图中有一个有向环
   • 删掉构成环的边就行了（和上题差不多）

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[][] edges = new int[n][2];int[] inDegree = new int[n + 1];for (int i = 0; i < n; i++) {int from = in.nextInt();int to = in.nextInt();// 节点to的入度加一inDegree[to]++;edges[i][0] = from;edges[i][1] = to;}// 检查edges中是否有入度为2的节点List<Integer> twoInDegree = new ArrayList<>();// 因为要满足情况一，优先输出后加入的边，需要倒序遍历for (int i = n - 1; i >= 0; i--) {if (inDegree[edges[i][1]] == 2) {// 这里加的这个i是edges中的索引twoInDegree.add(i);}}// 索引值int i;if (twoInDegree.size() > 0) {// 这条是最后加入的边i = twoInDegree.get(0);// 如果删除后仍能构成树，证明是情况一，直接删这条if (isTreeAfterRemove(edges, i, new Disjoint(n))) {} else {// 如果不能构成树，证明是情况二，删另一条i = twoInDegree.get(1);}} else {// 如果没有入度为2的边，走到这里，就是情况三：删除构成有向环的边// 注意，不要传用过的并查集。这里要传一个新的。i = getRemoveEdge(edges, new Disjoint(n));}// 打印输出System.out.println(edges[i][0] + " " + edges[i][1]);}// 模拟删除索引为Index这条边，看看剩下的边是否能构成树private static boolean isTreeAfterRemove(int[][] edges, int index, Disjoint dj) {for (int i = 0; i < edges.length; i++) {// 模拟删除索引为Index这条边，看看剩下的边是否能构成树if (i == index) {continue;}int from = edges[i][0];int to = edges[i][1];// 剩下的from to，还有不在一个图中的，证明存在孤点if (dj.isSame(from, to)) {return false;}dj.join(from, to);}// 模拟删除后，仍然能构成树return true;}// 情况三：删除构成有向环的边。和108冗余的边是一样的操作。private static int getRemoveEdge(int[][] edges, Disjoint dj) {int i=0;for (i = 0; i < edges.length; i++) {int from = edges[i][0];int to = edges[i][1];if (dj.isSame(from, to)) {break;} else {dj.join(from, to);}}return i;}
}// 并查集
class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 0; i <= n; i++) {father[i] = i;}}public int find(int a) {if (a == father[a]) {return a;} else {return father[a] = find(father[a]);}}public boolean isSame(int o1, int o2) {return find(o1) == find(o2);}public void join(int o1, int o2) {int root1 = find(o1);int root2 = find(o2);if (root1 == root2) {return;}father[o2] = o1;}
}

代码随想录中，给出的Java的版本，写得有点累赘。本篇代码改自卡尔的C++版本题解，自认为写得更加清晰一点。符合卡尔解题的时候用的思路。