蓝桥杯算法题-发现环
问题描述
小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时,管理员误操作使得某两台电脑之间增加了一条数据链接,于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径,使得这些电脑上的数据传输出现了BUG。为了恢复正常传输。小明需要找到所有在环路上的电脑,你能帮助他吗?
输入格式
第一行包含一个整数N。
以下N行每行两个整数a和b,表示a和b之间有一条数据链接相连。对于30%的数据,1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N输入保证合法。
输出格式
按从小到大的顺序输出在环路上的电脑的编号,中间由一个空格分隔。
样例输入
5
1 2
3 1
2 4
2 5
5 3
样例输出
1 2 3 5
思路:这道题打的标签似乎是并查集加DFS,不过我的并查集思路可能有点问题,有空再仔细想一下,可以看下下面这个博客
http://t.csdnimg.cn/LSVct
我看了另一个网友的题解,思路是用度来把叶子结点一个个剪掉,最后会剩下一个环,代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int g[N];
vector<int>a[N];
int main(){int n;cin>>n;int u,v;for(int i=0;i<n;i++){cin>>u>>v;g[u]++;g[v]++;a[u].push_back(v);a[v].push_back(u);//双向边}queue<int>q;//存叶子结点for(int i=1;i<=n;i++){if(g[i]==1)q.push(i);} while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<a[u].size();i++){g[a[u][i]]--;if(g[a[u][i]]==1)q.push(a[u][i]);}}for(int i=1;i<=n;i++){if(g[i]>1)cout<<i<<" ";}return 0;
}
相关文章:
蓝桥杯算法题-发现环
问题描述 小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时,管理员误操作使得某两台电脑之间增…...

Oracle存数字精度问题number、binary_double、binary_float类型
--表1 score是number(10,5)类型 create table TEST1 (score number(10,5) ); --表2 score是binary_double类型 create table TEST2 (score binary_double ); --表3 score是binary_float类型 create table TEST3 (score binary_float );实验一:分别往三张表插入 小数…...

Java封装最佳实践:打造高内聚、低耦合的优雅代码~
个人主页:秋风起,再归来~ 文章专栏:javaSE的修炼之路 个人格言:悟已往之不谏,知来者犹可追 克心守己,律己则安! 1、封装 1.1 封装的概念 面向对象程序三大…...

开源,微信小程序-超级计算器T3000 简介
笔者于四年前自学微信小程序开发,这个超级计算器T3000就是当时的练习作品。超级计算器T3000的功能有很多,其中的核心技术是矩阵计算,使用的工具库是math.js,其次是复杂运算和分式运算。关于math.js的使用,可以参考另一…...

Dimitra:基于区块链、AI 等前沿技术重塑传统农业
根据 2023 年联合国粮食及农业组织(FAO)、国际农业发展基金(IFAD)等组织联合发布的《世界粮食安全和营养状况》报告显示,目前全球约有 7.35 亿饥饿人口,远高于 2019 年的 6.13 亿,这意味着农业仍…...

降低项目延期概率的5大注意事项
降低项目延期概率对项目非常重要。因为项目延期往往会导致成本增加,降低客户满意度,影响企业在市场上的竞争力,造成资源浪费。因此,我们需要降低项目延期概率,实现企业长远发展。 而降低项目延期概率,一般来…...
在VUE页面调用Extjs中定义的方法
VUE版本:VUE2 EXTJS版本:4.2.6 1、在extjs页面上写监听事件(主要利用了window.addEventListener来监听message事件 window.addEventListener("message", function(event) {// 这里写监听到消息后的逻辑,event.data就是…...
【独立开发前线】Vol.32 能够坚持下去的人并没有你想象的那么多
如果你有一个博客,你就已经超过了80%的独立开发者; 如果你每周更新自己的博客,你就已经超过了90%的独立开发者; 如果你每天更新自己的博客,你就已经超过了99%的独立开发者; 能够坚持下去的人并没有你想象…...

Java 扫描某包下所有类的注解并获得注解值
背景 : 需求 需要获取某个包下的所有的注解 并不是全部项目的 所以 只用针对某个包 进行扫描 获取注解 数据就行 百度了一圈 spring boot 没有自带的 获取注解集合的方法 在看 php 中 hyperf 框架 看到了 这个方法 就是因为 我需求是 php 和java 合体 微服务开发 …...

根据实例逐行分析NIO到底在做什么
Selector(选择器)是 Channel 的多路复用器,它可以同时监控多个 Channel 的 IO 状况,允许单个线程来操作多个 Channel。Channel在从Buffer中获取数据。 选择器、通道、缓冲池是NIO的核心组件。 一、新建选择器 此时选择器内只包含…...
TypeScript-对象的类型(接口)
1.接口 说明:TypeScript 中的接口(Interfaces)是一种用来定义对象的结构或者契约的方式。通过接口,你可以定义对象应该具有哪些属性、方法以及它们的类型。 2.一致性 说明:接口的属性名和对象的属性名必须一致性。 …...

Windows服务器安全策略配置几个步骤,轻松加强服务器安全
Windows服务器安全策略怎么做?不要觉得这是一个非常深奥遥不可及的问题,其实也是从各个方面去加固系统的安全性而已,它没有一个定论,今天德迅云安全就跟用户们分享一下windows服务器基本安全策略保障服务器基本安全的一些简单实用…...
Hive详解(2)
Hive 表结构 分区表 多字段分区:需要使用多个字段来进行分区,那么此时字段之间会构成多层目录,前一个字段形成的目录会包含后一个字段形成的目录,从而形成多级分类的效果。例如商品的大类-小类-子类, 省市县、年…...

【浅尝C++】STL第二弹=>迭代器失效详解/vector常用接口使用示例/vector底层结构探索/vector模拟实现代码详解
🏠专栏介绍:浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 🎯每日格言:每日努力一点点,技术变化看得见。 文章目录 vector介绍vector常用接口及使用示例构造类函数迭代器的使用容量操作增删改查 迭代器失效详解与v…...
【pytest】pytest` 中几种常用的参数化方法
pytest 是一个强大的 Python 测试框架,它提供了多种参数化测试的方法。参数化测试允许你使用不同的输入集来运行相同的测试逻辑,从而确保代码在各种条件下都能正常工作。以下是 pytest 中几种常用的参数化方法: 1. 使用 pytest.mark.paramet…...

设计模式-装饰者模式在Java中使用实例-打印发票装饰抬头和脚注
场景 设计模式-装饰者模式在Java中的使用示例: 设计模式-装饰者模式在Java中的使用示例_java装饰者模式例子-CSDN博客 上面装饰器的调用示例如下 AbstarctComputer computer;//要买1台电脑computer new BaseComputer();//加一个内存条computer new MemoryDecor…...

parallel linux虚拟机没有root权限
前言 今天刚在parallel上装上linux虚拟机,安装的是Debian发行版。用终端输入命令时,无意间发现当前用户竟然不是root用户,岂有此理!众所周知,Linux系统一般安装之后都是默认root用户的,但是可能parallel先…...

科技下乡:数字乡村改变乡村生活方式
在科技飞速发展的时代,数字化、信息化浪潮正以前所未有的速度席卷全球。在这场科技革命中,乡村不再是滞后的代名词,而是成为了数字乡村建设的热土。科技下乡,让数字乡村成为了改变乡村生活方式的重要力量。 一、科技下乡…...
【GitLab】Ubuntu使用宝塔安装GitLab最新社区版
首先在Ubuntu安装宝塔面板 在官网可以找到脚本一键安装 安装GitLab社区版 然后在宝塔面板的“软件商店”里面找到GitLab最新社区版 12.8.1一键安装 安装过程中可能出现以下问题: 1.卡在ruby_block[wait for logrotate service socket] action run 解决办法&…...

C++入门(2)
目录 3. C输入&输出 4. 缺省(默认)参数 4.1 缺省参数概念 4.2 缺省参数分类 全缺省参数 半缺省参数 5. 函数重载 5.1 函数重载概念 6. 引用 6.1 引用概念 6.2 引用特性 6.3 常引用 6.4 使用场景 6.5 传值、传引用效率比较 6.5.1 值和引用的作为返回值类型的性能比较 6.6 引…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...

MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...

相关类相关的可视化图像总结
目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系,可直观判断线性相关、非线性相关或无相关关系,点的分布密…...

echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式
pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图,如果边框加在dom上面,pdf-lib导出svg的时候并不会导出边框,所以只能在echarts图上面加边框 grid的边框是在图里…...
raid存储技术
1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划,涵盖存储系统的布局、数据存储策略等,它明确数据如何存储、管理与访问,为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...