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

108. 冗余连接

题目链接：KamaCoder
文档讲解：代码随想录
状态：AC

---

Java代码：

import java.util.*;class Main {public static int[] father;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();father = new int[n + 1];init();String result = "";for (int i = 0; i < n; i++) {int s = scan.nextInt();int t = scan.nextInt();if (isSame(s, t)) {result = s + " " + t;} else {join(s, t);}}scan.close();System.out.println(result);}// 并查集初始化public static void init() {for (int i = 0; i < father.length; i++) {father[i] = i; // 每个节点的父节点初始化为自己}}// 并查集查找 (带路径压缩)public static int find(int u) {if (u == father[u]) {return u;}return (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) {father[v] = u; // 将 v 的根节点指向 u}}
}

---

109. 冗余连接II

题目链接：KamaCoder
文档讲解：代码随想录
状态：没做出来

---

Java代码：

import java.util.*;public class Main {/*** 并查集模板*/static class Disjoint {private final int[] father;public Disjoint(int n) {father = new int[n];for (int i = 0; i < n; i++) {father[i] = i;}}public void join(int n, int m) {n = find(n);m = find(m);if (n == m) return;father[n] = m;}public int find(int n) {return father[n] == n ? n : (father[n] = find(father[n]));}public boolean isSame(int n, int m) {return find(n) == find(m);}}static class Edge {int s;int t;public Edge(int s, int t) {this.s = s;this.t = t;}}static class Node {int id;int in;int out;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();List<Edge> edges = new ArrayList<>();Node[] nodeMap = new Node[n + 1];for (int i = 1; i <= n; i++) {nodeMap[i] = new Node();}Integer doubleIn = null;for (int i = 0; i < n; i++) {int s = scanner.nextInt();int t = scanner.nextInt();//记录入度nodeMap[t].in++;if (!(nodeMap[t].in < 2)) doubleIn = t;Edge edge = new Edge(s, t);edges.add(edge);}Edge result = null;//存在入度为2的节点，既要消除入度为2的问题同时解除可能存在的环if (doubleIn != null) {List<Edge> doubleInEdges = new ArrayList<>();for (Edge edge : edges) {if (edge.t == doubleIn) doubleInEdges.add(edge);if (doubleInEdges.size() == 2) break;}Edge edge = doubleInEdges.get(1);if (isTreeWithExclude(edges, edge, nodeMap)) {result = edge;} else {result = doubleInEdges.get(0);}} else {//不存在入度为2的节点,则只需要解除环即可result = getRemoveEdge(edges, nodeMap);}System.out.println(result.s + " " + result.t);}public static boolean isTreeWithExclude(List<Edge> edges, Edge exculdEdge, Node[] nodeMap) {Disjoint disjoint = new Disjoint(nodeMap.length + 1);for (Edge edge : edges) {if (edge == exculdEdge) continue;//成环则不是树if (disjoint.isSame(edge.s, edge.t)) {return false;}disjoint.join(edge.s, edge.t);}return true;}public static Edge getRemoveEdge(List<Edge> edges, Node[] nodeMap) {int length = nodeMap.length;Disjoint disjoint = new Disjoint(length);for (Edge edge : edges) {if (disjoint.isSame(edge.s, edge.t)) return edge;disjoint.join(edge.s, edge.t);}return null;}}