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

news/2025/2/12 0:48:25/

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个调用方法的代码

http://www.ppmy.cn/news/1571283.html

相关文章

Vue 3 30天精进之旅:Day 16 - 组合式API进阶

友情提示&#xff1a;本文内容全部由 银河易创&#xff08;https://ai.eaigx.com&#xff09;AI创作平台生成&#xff0c;仅供参考。请根据具体情况和需求进行适当的调整和验证。 欢迎来到“Vue 3 30天精进之旅”的第16天&#xff01;今天我们将深入探讨 组合式API 的进阶用法&…

如何在WPS和Word/Excel中直接使用DeepSeek功能

以下是将DeepSeek功能集成到WPS中的详细步骤&#xff0c;无需本地部署模型&#xff0c;直接通过官网连接使用&#xff1a;1. 下载并安装OfficeAI插件 &#xff08;1&#xff09;访问OfficeAI插件下载地址&#xff1a;OfficeAI助手 - 免费办公智能AI助手, AI写作&#xff0c;下载…

matlab simulink 船舶模糊pid控制仿真

1、内容简介 略 matlab simulink 118-船舶模糊pid控制仿真 可以交流、咨询、答疑 2、内容说明 略 3、仿真分析 略 4、参考论文 略 基于船舶运动控制的Matlab仿真.pdf

Linux系统编程之信号基础知识

概述 信号是Linux系统中用于进程间通信的一种机制&#xff0c;允许一个进程通知另一个进程发生了某些特定事件。信号可以来自硬件中断、用户输入&#xff0c;也可以来自其他进程或者内核本身。信号是一种异步通知机制&#xff0c;当某个事件发生时&#xff0c;操作系统会向目标…

【小鱼闪闪】自制物联网测温小程序远程监测温度(图文)

小飞鱼之前写过一个将测温元件读取数据后写入到本地服务器的程序&#xff0c;可是这样有一个缺点就是只能局限于局域网来查询数据&#xff0c;而对于在办公楼外就不能查看数据。为了解决这个问题&#xff0c;今天小飞鱼做了一个可以将温度数据写入到云端的程序&#xff0c;再通…

【漫话机器学习系列】086.机器学习中的能力(Capacity)

机器学习中的能力&#xff08;Capacity&#xff09; 1. 引言 在机器学习中&#xff0c;模型的能力&#xff08;Capacity&#xff09;是一个重要的概念&#xff0c;它决定了模型能够学习的函数复杂度。简单来说&#xff0c;能力衡量了一个模型拟合不同函数的能力。能力越强的模…

和鲸科技上线 DeepSeek 系列模型服务,助力数智企业 AI 业务创新!

近日&#xff0c;和鲸科技团队宣布旗下数据科学协同平台 ModelWhale 实现对 DeepSeek 全系列大模型的深度支持&#xff0c;旨在帮助更多数智化转型企业提供从算力基建到业务融合的全栈式解决方案&#xff0c;快速搭建自主可控的云端智能服务体系&#xff0c;实现大模型与业务系…

数据库创库建表处理

新建数据库 mysql> create database mydb15_indexstu; Query OK, 1 row affected (0.03 sec)mysql> use mydb15_indexstu; Database changed 新建表 创建学生信息表 mysql> create table Student( Sno int primary key auto_increment, Sname varchar(30) not nul…