108.冗余连接

思路：从前向后遍历每一条边，边的两个节点如果不在同一个集合，就加入集合；如果边的两个节点已经出现在同一个集合里，说明边的两个节点已经连在一起了，再加入这条边一定会出现环。

代码如下：

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();DisJoint disJoint=new DisJoint(n+2);for(int i=0;i<n;i++){int u=scan.nextInt();int v=scan.nextInt();if(!disJoint.isSame(u,v)) disJoint.join(u,v);else System.out.println(u+" "+v);}}}class DisJoint{private int[] father;public DisJoint(int N){father=new int[N];for(int i=0;i<N;i++){father[i]=i;}}public int find(int n){return father[n]==n?n: (father[n]=find(father[n]));}public boolean isSame(int u,int v){u=find(u);v=find(v);return u==v;}public void join(int u,int v){u=find(u);v=find(v);if(u==v) return;father[v]=u;}
}

109.冗余连接II

有向图比无向图相对复杂，考虑多种情况：

• 情况一：如果找到入度为2的点，需要判断删除哪一条边，删除后本图能成为有向树。如果是删哪个都可以，优先删顺序靠后的边。
• 情况二： 如果没有入度为2的点，说明图中有环，删掉构成环的边。

代码如下：

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan=new Scanner(System.in);int n=scan.nextInt();List<int[]> edge=new ArrayList<>();int[] inDegree=new int[n+1];DisJoint disJoint=new DisJoint(n+1);List<int[]> possibleEdges = new ArrayList<>();for (int i = 0; i < n; i++) {int s = scan.nextInt();int t = scan.nextInt();edge.add(new int[]{s, t});inDegree[t]++;if (!disJoint.isSame(s,t)) {disJoint.join(s,t);}else possibleEdges.add(new int[]{s, t});}// 寻找入度为2的节点int conflictNode = -1;for (int i = 1; i <= n; i++) {if (inDegree[i] == 2) {conflictNode = i;break;}}// 如果存在入度为2的节点，逆向查找多余的边if (conflictNode != -1) {for (int i = n - 1; i >= 0; i--) {if (edge.get(i)[1] == conflictNode) {// 尝试删除这条边，检查是否还能构成有向树if (checkTree(edge, i)) {System.out.println(edge.get(i)[0] + " " + edge.get(i)[1]);return;}}}}// 如果存在可能的边，选择最后出现的那条边if (!possibleEdges.isEmpty()) {int[] lastEdge = possibleEdges.get(possibleEdges.size() - 1);System.out.println(lastEdge[0] + " " + lastEdge[1]);}}// 检查删除某条边后是否还能构成有向树private static boolean checkTree(List<int[]> edge, int removeIndex) {int n = edge.size();DisJoint disJoint = new DisJoint(n + 1);Set<Integer> nodes = new HashSet<>();for (int i = 0; i < n; i++) {if (i == removeIndex) continue;int s = edge.get(i)[0];int t = edge.get(i)[1];nodes.add(s);nodes.add(t);if (disJoint.isSame(s, t)) {return false; // 形成环} else {disJoint.join(s, t);}}// 检查是否所有节点都在同一个连通分量中for (int i = 1; i <= n; i++) {if (nodes.contains(i) && !disJoint.isSame(1, i)) {return false; // 不是连通的}}return true;}
}
class DisJoint{private int[] father;public DisJoint(int N){father=new int[N];for(int i=0;i<N;i++){father[i]=i;}}public int find(int n){return father[n]==n?n: (father[n]=find(father[n]));}public boolean isSame(int u,int v){u=find(u);v=find(v);return u==v;}public void join(int u,int v){u=find(u);v=find(v);if(u==v) return;father[v]=u;}}