代码随想录算法训练营第六十二天 | 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]);}}
}

老是忘记初始化并查集。