Day 60 || 108.冗余连接 、109.冗余连接II

题目链接： 卡码网题目链接（ACM模式）

思路：利用“并查集 ”的思路，可以理解为加入的这个边，如果边上的二者能找到共同的父节点就证明这个边是多余的，打印出这个边即可。

109.  冗余连接II

• 需要找到的是入度为2的边删除一条后是否成立，因为有要求“每一个节点都有且只有一个父节点”，删除一条边后要判断是否满足“所有其他节点都是该根节点的后继”，因为有可能会独立一个点。
• 还有可能是存在一个环，且这个环导致“每一个节点都有且只有一个父节点”不满足，所以这个环删除最后一个使其成环的边即可。

以上两个情况相互独立。（代码来自“代码随想录”）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {static int n;static int[] father = new int[1001]; // 并查集数组// 并查集初始化public static void init() {for (int i = 1; i <= n; ++i) {father[i] = i;}}// 并查集里寻根的过程public static int find(int u) {if (u == father[u]) return u;return father[u] = find(father[u]); // 路径压缩}// 将 v->u 这条边加入并查集public static void join(int u, int v) {u = find(u);v = find(v);if (u != v) {father[v] = u; // 合并两棵树}}// 判断 u 和 v 是否有同一个根public static boolean same(int u, int v) {return find(u) == find(v);}// 在有向图里找到删除的那条边，使其变成树public static void getRemoveEdge(List<int[]> edges) {init(); // 初始化并查集for (int i = 0; i < n; i++) { // 遍历所有的边if (same(edges.get(i)[0], edges.get(i)[1])) { // 如果构成有向环了，就是要删除的边System.out.println(edges.get(i)[0] + " " + edges.get(i)[1]);return;} else {join(edges.get(i)[0], edges.get(i)[1]);}}}// 删一条边之后判断是不是树public static boolean isTreeAfterRemoveEdge(List<int[]> edges, int deleteEdge) {init(); // 初始化并查集for (int i = 0; i < n; i++) {if (i == deleteEdge) continue;if (same(edges.get(i)[0], edges.get(i)[1])) { // 如果构成有向环了，一定不是树return false;}join(edges.get(i)[0], edges.get(i)[1]);}return true;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);List<int[]> edges = new ArrayList<>(); // 存储所有的边n = sc.nextInt(); // 顶点数int[] inDegree = new int[n + 1]; // 记录每个节点的入度for (int i = 0; i < n; i++) {int s = sc.nextInt(); // 边的起点int t = sc.nextInt(); // 边的终点inDegree[t]++;edges.add(new int[]{s, t}); // 将边加入列表}List<Integer> vec = new ArrayList<>(); // 记录入度为2的边（如果有的话就两条边）// 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边for (int i = n - 1; i >= 0; i--) {if (inDegree[edges.get(i)[1]] == 2) {vec.add(i);}}// 情况一、情况二if (vec.size() > 0) {// vec里的边已经按照倒叙放的，所以优先删 vec.get(0) 这条边if (isTreeAfterRemoveEdge(edges, vec.get(0))) {System.out.println(edges.get(vec.get(0))[0] + " " + edges.get(vec.get(0))[1]);} else {System.out.println(edges.get(vec.get(1))[0] + " " + edges.get(vec.get(1))[1]);}return;}// 处理情况三：明确没有入度为2的情况，一定有有向环，找到构成环的边返回即可getRemoveEdge(edges);}
}