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

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

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

题目

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

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

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

输入示例

3
1 2
2 3
1 3

输出示例

1 3

思路

• 思路
  • 题意转化为并查集
    • 当存在两个顶点处于同一个集合时，重复2次，说明有冗余边，删除最后一个。
    • 代码，初始化DisJoint,用join将两个顶点建立一个集合，然后用isSame判断两个不在1个集合中的顶点是否在一个集合中，并且判断两个在1个集合中的顶点是否重复加入了
• 代码

  import java.util.*;
  public class Main{public static void main(String[] args){//输入Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();DisJoint disJoint=new DisJoint(n+1);int[][] edges=new int[n][2];//m条边for(int i=0;i<n;i++){edges[i][0]=scanner.nextInt();edges[i][1]=scanner.nextInt();}for(int i=0;i<n;i++){int u=edges[i][0];int v=edges[i][1];//先检查是否冗余：如果2个节点在同一集合中，【本身已经连通，才会输出冗余边】if(disJoint.isSame(u,v)){System.out.println(u+" "+v);return;}//不冗余的话将2个边加入到同一集合中disJoint.join(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 n==father[n]?n:(father[n]=find(father[n]));}//将2个节点加入到同一个集合中public void join(int n,int m){n=find(n);m=find(m);if(n==m) return;father[m]=n;}//判断2个节点是否在同一个集合中public boolean isSame(int n,int m){return find(n)==find(m);}
  }

总结

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

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

题目

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

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

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

输入描述

第一行输入一个整数 N，表示有向图中节点和边的个数。

后续 N 行，每行输入两个整数 s 和 t，代表这是 s 节点连接并指向 t 节点的单向边

输出描述

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

输入示例

3
1 2
1 3
2 3

输出示例

2 3

提示信息

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

数据范围：

1 <= N <= 1000.

思路

• 思路
  • 与上一题的区别是，有向图
    • 有向树，根节点入度为0，其他节点入度都为1。
  • 核心：如果我们找到入度为2的点，那么删一条指向该节点的边就行了。
  • 注意特殊情况：
    • 
      • 节点3的入度为2，但在删除边的时候，只能删(1到3)，如果删(4-3)，就不是有向树了(找不到根节点)。
      • 如果发现入度为2的节点，判断删除哪一条边，才能成为有向树，如果是删哪个都可以，优先删除顺序靠后的边。
    • 如果没有入度为2的点，说明图中有环了(有向环)。
      • 删除构成环的边就可以了。
• 伪代码
  • 将每条边记录下来，并统计入度。
  • 情况1和情况2，从后向前遍历，如果有入度为2的情况，删除一条边后判断这个图是一个图，那么这条边是答案。如果删除哪条边都可以成为树，就删除最后那一条。
  • 如果没有入度为2的情况，一定有有向环，找到构成环的边就是要删除的边
• 代码

  import java.util.*;public class Main {//并查集Disjoint类static class Disjoint {private int[] father;public Disjoint(int n) {father = new int[n + 1];for (int i = 1; i <= n; i++) {father[i] = i;}}public int find(int n) {if (father[n] != n) {father[n] = find(father[n]); // 路径压缩}return father[n];}public void join(int n, int m) {father[find(n)] = find(m);}public boolean isSame(int n, int m) {return find(n) == find(m);}}public static void main(String[] args) {//输入Scanner scanner = new Scanner(System.in);//scannerint n = scanner.nextInt();int[][] edges = new int[n][2]; //边int[] inDegree = new int[n + 1]; //入度Integer doubleInNode = null;//存储入度为2的节点// 读取输入并统计入度for (int i = 0; i < n; i++) {edges[i][0] = scanner.nextInt();edges[i][1] = scanner.nextInt();inDegree[edges[i][1]]++;//如果度为2，记录该节点if (inDegree[edges[i][1]] == 2) doubleInNode = edges[i][1]; }//case1:存在入度为2的节点//找到2条指向doubleNode的边，存入candidates[][]if (doubleInNode != null) {int[][] candidates = new int[2][2];int index = 0;for (int i = 0; i < n; i++) {if (edges[i][1] == doubleInNode) {candidates[index++] = edges[i];if (index == 2) break;}}// 先尝试删除第2条边(candidates[1]),如果删除后形成树，输出candidates[1]，否则输出candidates[0]if (isTreeAfterRemoving(edges, candidates[1], n)) {System.out.println(candidates[1][0] + " " + candidates[1][1]);} else {System.out.println(candidates[0][0] + " " + candidates[0][1]);}return;}//case2:不存在度为2(环)，找出最后一条导致环的边int[] lastEdge = getLastEdgeToRemove(edges, n);System.out.println(lastEdge[0] + " " + lastEdge[1]);}// 方法 1：删除某条边后是否形成树private static boolean isTreeAfterRemoving(int[][] edges, int[] excludeEdge, int n) {Disjoint disjoint = new Disjoint(n);//检查环for (int i = 0; i < n; i++) {// **优化点：直接比较两个值，而不是 Arrays.equals**//if当前边是要删除的边(2个点)，继续(continue);if (edges[i][0] == excludeEdge[0] && edges[i][1] == excludeEdge[1]) continue;//检查是否形成环//如果起点和终点已经在同一个集合，说明形成了环if (disjoint.isSame(edges[i][0], edges[i][1])) {return false; }//合并2个节点disjoint.join(edges[i][0], edges[i][1]);}return true;}// 方法 2：找到最后出现的环边//在有向图中找到最后一条导致环的边，并返回该边private static int[] getLastEdgeToRemove(int[][] edges, int n) {Disjoint disjoint = new Disjoint(n);int[] lastEdge = null;//记录最后一条导致环的边for (int i = 0; i < n; i++) {//检查是否形成环//如果起点和终点已经在同一集合，形成了环if (disjoint.isSame(edges[i][0], edges[i][1])) {lastEdge = edges[i]; //更新存储的边} else {//合并到1个集合中disjoint.join(edges[i][0], edges[i][1]);}}return lastEdge;}
  }

总结

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