图论day60|108.冗余连接(卡码网) 、109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】
图论day60|108.冗余连接(卡码网)、109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】
- 108.冗余连接(卡码网)
- 109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】
108.冗余连接(卡码网)
题目描述
有一个图,它是一棵树,他是拥有 n 个节点(节点编号1到n)和 n - 1 条边的连通无环无向图(其实就是一个线形图),如图:

现在在这棵树上的基础上,添加一条边(依然是n个节点,但有n条边),使这个图变成了有环图,如图:

先请你找出冗余边,删除后,使该图可以重新变成一棵树。
输入描述
第一行包含一个整数 N,表示图的节点个数和边的个数。
后续 N 行,每行包含两个整数 s 和 t,表示图中 s 和 t 之间有一条边。
输出描述
输出一条可以删除的边。如果有多个答案,请删除标准输入中最后出现的那条边。
输入示例
3
1 2
2 3
1 3
输出示例
1 3
提示信息

图中的 1 2,2 3,1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边,所以输出结果为 1 3
数据范围:
1 <= N <= 1000.

#include <iostream>
#include <vector>
using namespace std;int n;
vector<int> father(1001,0);void init()
{for(int i=1;i<=n;i++)father[i]=i;
}int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}bool isSame(int u,int v)
{u=find(u);v=find(v);return u==v;
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return;elsefather[v]=u;
}int main()
{cin>>n;init();int s,t;for(int i=0;i<n;i++){cin>>s>>t;if(isSame(s,t)){cout<<s<<" "<<t<<endl;return 0;}elsejoin(s,t);}
}
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.

#include <iostream>
#include <vector>
using namespace std;int n;
vector<int> father(1001,0);void init()
{for(int i=1;i<=n;i++)father[i]=i;
}int find(int u)
{return u==father[u]?u:father[u]=find(father[u]);
}bool isSame(int u,int v)
{u=find(u);v=find(v);return u==v;
}void join(int u,int v)
{u=find(u);v=find(v);if(u==v)return;elsefather[v]=u;
}bool deleteIsTree(vector<vector<int>> edges,int x)
{init();for(int i=0;i<n;i++){if(i==x) continue;if(isSame(edges[i][0],edges[i][1]))return false;elsejoin(edges[i][0],edges[i][1]);}return true;
}void removeEdge(vector<vector<int>> edges)
{init();for(int i=0;i<n;i++){if(isSame(edges[i][0],edges[i][1]))cout<<edges[i][0]<<" "<<edges[i][1]<<endl;elsejoin(edges[i][0],edges[i][1]);}
}int main()
{int s,t;cin>>n;vector<vector<int>> edges;vector<int> inDegree(n+1,0);vector<int> vec;for(int i=0;i<n;i++){cin>>s>>t;edges.push_back({s,t});inDegree[t]++;}for(int i=n-1;i>0;i--){if(inDegree[edges[i][1]]==2)vec.push_back(i);}if(vec.size()>0){if(deleteIsTree(edges,vec[0]))cout<<edges[vec[0]][0]<<" "<<edges[vec[0]][1]<<endl;elsecout<<edges[vec[1]][0]<<" "<<edges[vec[1]][1]<<endl;return 0;}removeEdge(edges);
}
相关文章:
图论day60|108.冗余连接(卡码网) 、109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】
图论day60|108.冗余连接(卡码网)、109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】 108.冗余连接(卡码网)109.冗余连接II(卡码网)【并查集 摧毁…...
即使是编程新手,也能利用ChatGPT编写高质量的EA
在外汇交易领域,MetaTrader是一款备受欢迎的交易软件,包括MT5和MT4,提供了众多强大的分析工具和自动化交易功能。对于没有编程经验的新手而言,编写专家顾问(EA)可能显得既复杂又令人望而却步。幸运的是&…...
StarRocks大批量数据导入方案-使用 Routine Load 导入数据
本文详细介绍如何使用Routine Load 导入数据 一、准备工作 1.1 安装基础环境 主要是安装StarRocks和Kafka,本文直接跳过不做详细介绍~ 二、概念及原理 2.1 概念 导入作业(Load job) 导入作业会常驻运行,当导入作业的状态为 R…...
从零开始学PHP之输出语句变量常量
一、 输出方式 在 PHP 中输出方式: echo,print,print_r,var_dump 1、echo和print为php的输出语句 2、var_dump,print_r为php的输出函数 (这里不做介绍)echo 和 print 区别 1、echo - 可以输出…...
二叉树算法之字典树(Trie)详细解读
字典树(Trie,也称前缀树或单词查找树)是一种用于快速查找字符串的数据结构,主要应用于字符串集合的高效存储和查找。字典树特别适合处理具有相同前缀的大量字符串集合,比如单词自动补全、拼写检查等场景。 1. 字典树的…...
butterfly侧边栏音乐模块
方法1.美观但换页后没法播放 1.blog根目录/source文件夹下新建_data文件夹(如果没有_data文件夹) 2.在刚刚的_data文件夹里创建widget.yml文件 bottom:- class_name: user-musicid_name: user-musicname: 音乐icon: fas fa-heartbeatorder:html: <…...
【论文阅读】Detach and unite: A simple meta-transfer for few-shot learning
分离与联合:一种用于小样本学习的简单元迁移方法 引用:Zheng Y, Zhang X, Tian Z, et al. Detach and unite: A simple meta-transfer for few-shot learning[J]. Knowledge-Based Systems, 2023, 277: 110798. 论文地址:下载地址 论文代码&a…...
Java中的动态代理——介绍与使用示例
Java中的动态代理其实就是一种“代理”模式,在运行时帮我们创建一个“代理对象”,通过这个代理对象可以在不改变原本方法的情况下,做一些额外的事情,比如记录日志、检查权限等。这种代理机制非常灵活和实用,特别是在像…...
微信开发者工具:音乐小程序报错
报错信息 GET http://localhost:3000/1.mp3 net::ERR CONNECTION REFUSED (env: Windows,mp,1.06.2303220;lib:3.6.0) 原因:小程序没有直接获取本地文件,为了提高访问速度,而采用放到网络服务器中网络访问的方式获取文件内容 解决办法&#…...
P2-3与P2-4.【C语言基本数据类型、运算符和表达式】第三节与第四节
讲解视频: P2-3.【基本数据类型、运算符和表达式】第三节 P2-4.【基本数据类型、运算符和表达式】第四节 目录 必备知识与理论 任务实施 必备知识与理论 C语言中把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理。 其运算符和表达式数量之多&a…...
Python | Leetcode Python题解之第492题构造矩形
题目: 题解: class Solution:def constructRectangle(self, area: int) -> List[int]:w int(sqrt(area))while area % w:w - 1return [area // w, w]...
新版vs code + Vue高亮、语法自动补全插件
vs code 版本或及以上 安装以下三个插件插件 Vetur Vue语法支持。包括语法高亮、语法代码提示、语法lint检测 ESLint语法纠错 Prettier 2.左下角设置 3.进行配置 配置内容: {"editor.fontSize": 20,"window.zoomLevel": 1,"workben…...
【优选算法】(第四十五篇)
目录 地图分析(medium) 题目解析 讲解算法原理 编写代码 课程表(medium) 题目解析 讲解算法原理 编写代码 地图分析(medium) 题目解析 1.题目链接:. - 力扣(LeetCode&#…...
自闭症儿童的康复与培养:揭秘有效方法
在生命的广阔画卷中,每一个孩子都是独一无二的色彩,他们带着各自的使命和梦想,踏上人生的旅程。然而,对于自闭症儿童而言,这段旅程似乎更加崎岖和艰难。幸运的是,星贝育园康复中心如同一盏明灯,…...
rom定制系列------小米8澎湃os1.0.28安卓13客户定制固件 刷写以及界面预览
💝💝💝 小米8后置指纹版,机型代码dipper, 官方最终版为12.5.2安卓10的版本。对于一些工作室不太适用。客户需要应用在安卓13的固件。根据客户提供的固件将卡刷改为线刷。并且修改其中客户需求。去除不需要的内置应用以…...
【CTF-SHOW】Web入门 Web14 【editor泄露-详】【var/www/html目录-详】
editor泄露问题通常出现在涉及文件编辑器或脚本编辑器的题目中,尤其是在Web安全或Pwn(系统漏洞挖掘)类别中。editor泄露的本质是由于系统未能妥善处理临时文件、编辑历史或进程信息,导致攻击者可以通过某种途径获取正在编辑的敏感…...
Chrome谷歌浏览器禁止空格下翻页但可以暂停和播放视频脚本js
前提 播放某些网站的视频的时候(不能网页全屏的视频) 会产生空格下翻页但是不能暂停播放视频,解决方案:下载油猴或者脚本猫把这代码填进去 (function() {use strict;document.body.onkeydown function(event) {var e window.event || event;// 检查是否按下空格…...
【笔记】【YOLOv10图像识别】自动识别图片、视频、摄像头、电脑桌面中的花朵学习踩坑
(一)启动 创建环境python3.9 打开此环境终端 (后面的语句操作几乎都在这个终端执行) 输入up主提供的语句:pip install -r requirements.txt 1.下载pytorch网络连接超时 pytorch网址: Start Locally | P…...
H-TCP 的效率和公平性
昨晚带安孩楼下玩耍,用手机 desmos 作了一组 response curve 置于双对数坐标系: 长肥管道的优化思路都很类似,cwnd 增长快一点: BIC TCP:二分查找逼近 capacity;CUBIC TCP:上凸曲线逼近 capa…...
集群与分布式
Cluster(集群)概述 当单独一台主机无法承载现有的用户请求量;或者一台主机因为单一故障导致业务中断的时候,就可以增加服务主机数,这些主机在一起提供服务,就叫集群,而用户所看到的依然是单个的主机,用户并…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
