Day62_补20250210_图论part6_108冗余连接|109.冗余连接II

Day62_20250210_图论part6_108冗余连接|109.冗余连接II

108冗余连接 【把题意转化为并查集题目】

题目

有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图（实在就是一个线形图），如图：

如今在这棵树上的根本上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图：

先请你找出冗余边，删除后，使该图可以重新变成一棵树。
输入示例

1. 3
2. 1 2
3. 2 3
5. 1 3

复制代码

输出示例

1. 1 3

复制代码

思绪

• 思绪
  
  
  
  • 题意转化为并查集
    
    
    
    • 当存在两个顶点处于同一个聚集时，重复2次，阐明有冗余边，删除最后一个。
      
    • 代码，初始化DisJoint,用join将两个顶点建立一个聚集，然后用isSame判断两个不在1个聚会合的顶点是否在一个聚会合，而且判断两个在1个聚会合的顶点是否重复加入了
      
    
    
  
  
• 代码
  1. import java.util.*;
  2. public class Main{
  3.     public static void main(String[] args){
  4.         //输入
  5.         Scanner scanner=new Scanner(System.in);
  6.         int n=scanner.nextInt();
  7.         DisJoint disJoint=new DisJoint(n+1);
  8.         int[][] edges=new int[n][2];//m条边
  9.    
  10.         for(int i=0;i<n;i++){
  11.             edges[i][0]=scanner.nextInt();
  12.             edges[i][1]=scanner.nextInt();
  13.         }
  14.         for(int i=0;i<n;i++){
  15.             int u=edges[i][0];
  16.             int v=edges[i][1];
  17.         
  18.             //先检查是否冗余：如果2个节点在同一集合中，【本身已经连通，才会输出冗余边】
  19.             if(disJoint.isSame(u,v)){
  20.                 System.out.println(u+" "+v);
  21.                 return;
  22.             }
  23.             //不冗余的话将2个边加入到同一集合中
  24.             disJoint.join(u,v);
  25.         }
  26.     }
  27. }
  28. class DisJoint{
  29.     private int[] father;//父节点
  30.     //初始化
  31.     public DisJoint(int N){
  32.         father=new int[N];
  33.         for(int i=0;i<N;i++){
  34.             father[i]=i;
  35.         }
  36.     }
  37.     //寻找根节点
  38.     public int find(int n){
  39.         return n==father[n]?n:(father[n]=find(father[n]));
  40.     }
  41.     //将2个节点加入到同一个集合中
  42.     public void join(int n,int m){
  43.         n=find(n);
  44.         m=find(m);
  45.         if(n==m) return;
  46.         father[m]=n;
  47.     }
  48.     //判断2个节点是否在同一个集合中
  49.     public boolean isSame(int n,int m){
  50.         return find(n)==find(m);
  51.     }
  52. }

  复制代码

总结

• 注意，题目中冗余的边的个数仅为1条。
  
• 思绪
  
  
  
  • 将2
    
  
  

109.冗余连接II 【难度上升】

题目

有一种有向树,该树只有一个根节点，全部其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。有向树拥有 n 个节点和 n - 1 条边。如图：

如今有一个有向图，有向图是在有向树中的两个没有直接链接的节点中间添加一条有向边。如图：

输入一个有向图，该图由一个有着 n 个节点(节点编号 从 1 到 n)，n 条边，请返回一条可以删除的边，使得删除该条边之后该有向图可以被当作一颗有向树。
输入形貌

第一行输入一个整数 N，表示有向图中节点和边的个数。
后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边
输出形貌

输出一条可以删除的边，若有多条边可以删除，请输出标准输入中最后出现的一条边。
输入示例

1. 31 21 3
2. 2 3

复制代码

输出示例

1. 2 3

复制代码

提示信息

在删除 2 3
后有向图可以变为一棵正当的有向树，所以输出 2 3

数据范围：
1 <= N <= 1000.
思绪

• 思绪
  
  
  
  • 与上一题的区别是，有向图
    
    
    
    • 有向树，根节点入度为0，其他节点入度都为1。
      
    
    
  • 核心：假如我们找到入度为2的点，那么删一条指向该节点的边就行了。
    
  • 注意特别环境：
    
    
    
    • 
      
      
      
      
      • 节点3的入度为2，但在删除边的时间，只能删(1到3)，假如删(4-3)，就不是有向树了(找不到根节点)。
        
      • 假如发现入度为2的节点，判断删除哪一条边，才能成为有向树，假如是删哪个都可以，优先删除次序靠后的边。
        
      
      
    • 假如没有入度为2的点，阐明图中有环了(有向环)。
      
      
      
      • 删除构成环的边就可以了。
        
      
      
    
    
  
  
• 伪代码
  
  
  
  • 将每条边记载下来，并统计入度。
    
  • 环境1和环境2，从后向前遍历，假如有入度为2的环境，删除一条边后判断这个图是一个图，那么这条边是答案。假如删除哪条边都可以成为树，就删除最后那一条。
    
  • 假如没有入度为2的环境，肯定有有向环，找到构成环的边就是要删除的边
    
  
  
• 代码
  1. import java.util.*;
  3. public class Main {
  4.     //并查集Disjoint类
  5.     static class Disjoint {
  6.         private int[] father;
  8.         public Disjoint(int n) {
  9.             father = new int[n + 1];
  10.             for (int i = 1; i <= n; i++) {
  11.                 father[i] = i;
  12.             }
  13.         }
  15.         public int find(int n) {
  16.             if (father[n] != n) {
  17.                 father[n] = find(father[n]); // 路径压缩
  18.             }
  19.             return father[n];
  20.         }
  22.         public void join(int n, int m) {
  23.             father[find(n)] = find(m);
  24.         }
  26.         public boolean isSame(int n, int m) {
  27.             return find(n) == find(m);
  28.         }
  29.     }
  31.     public static void main(String[] args) {
  32.         //输入
  33.         Scanner scanner = new Scanner(System.in);//scanner
  34.         int n = scanner.nextInt();
  35.         int[][] edges = new int[n][2]; //边
  36.         int[] inDegree = new int[n + 1]; //入度
  37.         Integer doubleInNode = null;//存储入度为2的节点
  39.         // 读取输入并统计入度
  40.         for (int i = 0; i < n; i++) {
  41.             edges[i][0] = scanner.nextInt();
  42.             edges[i][1] = scanner.nextInt();
  43.             inDegree[edges[i][1]]++;
  44.             //如果度为2，记录该节点
  45.             if (inDegree[edges[i][1]] == 2) doubleInNode = edges[i][1];
  46.         }
  48.         //case1:存在入度为2的节点
  49.         //找到2条指向doubleNode的边，存入candidates[][]
  50.         if (doubleInNode != null) {
  51.             int[][] candidates = new int[2][2];
  52.             int index = 0;
  53.             for (int i = 0; i < n; i++) {
  54.                 if (edges[i][1] == doubleInNode) {
  55.                     candidates[index++] = edges[i];
  56.                     if (index == 2) break;
  57.                 }
  58.             }
  60.             // 先尝试删除第2条边(candidates[1]),如果删除后形成树，输出candidates[1]，否则输出candidates[0]
  61.             if (isTreeAfterRemoving(edges, candidates[1], n)) {
  62.                 System.out.println(candidates[1][0] + " " + candidates[1][1]);
  63.             } else {
  64.                 System.out.println(candidates[0][0] + " " + candidates[0][1]);
  65.             }
  66.             return;
  67.         }
  69.         //case2:不存在度为2(环)，找出最后一条导致环的边
  70.         int[] lastEdge = getLastEdgeToRemove(edges, n);
  71.         System.out.println(lastEdge[0] + " " + lastEdge[1]);
  72.     }
  74.     // 方法 1：删除某条边后是否形成树
  75.     private static boolean isTreeAfterRemoving(int[][] edges, int[] excludeEdge, int n) {
  76.         Disjoint disjoint = new Disjoint(n);//检查环
  77.         for (int i = 0; i < n; i++) {
  78.             // **优化点：直接比较两个值，而不是 Arrays.equals**
  79.             //if当前边是要删除的边(2个点)，继续(continue);
  80.             if (edges[i][0] == excludeEdge[0] && edges[i][1] == excludeEdge[1]) continue;
  81.             //检查是否形成环
  82.             //如果起点和终点已经在同一个集合，说明形成了环
  83.             if (disjoint.isSame(edges[i][0], edges[i][1])) {
  84.                 return false;
  85.             }
  86.             //合并2个节点
  87.             disjoint.join(edges[i][0], edges[i][1]);
  88.         }
  89.         return true;
  90.     }
  92.     // 方法 2：找到最后出现的环边
  93.     //在有向图中找到最后一条导致环的边，并返回该边
  95.     private static int[] getLastEdgeToRemove(int[][] edges, int n) {
  96.         Disjoint disjoint = new Disjoint(n);
  97.         int[] lastEdge = null;//记录最后一条导致环的边
  100.         for (int i = 0; i < n; i++) {
  101.             //检查是否形成环
  102.             //如果起点和终点已经在同一集合，形成了环
  103.             if (disjoint.isSame(edges[i][0], edges[i][1])) {
  104.                 lastEdge = edges[i]; //更新存储的边
  105.             } else {
  106.                 //合并到1个集合中
  107.                 disjoint.join(edges[i][0], edges[i][1]);
  108.             }
  109.         }
  110.         return lastEdge;
  111.     }
  112. }

  复制代码

总结

• 这题好难，难在怎么写2个调用方法的代码
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。