day54 图论章节刷题Part06（108.冗余连接、109.冗余连接II）

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;
    }
    
}

原文地址：https://blog.csdn.net/m0_51007517/article/details/143607529

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！