当前位置: 首页 > news >正文

蓝桥杯算法题-发现环

问题描述
  小明的实验室有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台电脑&#xff0c;编号1~N。原本这N台电脑之间有N-1条数据链接相连&#xff0c;恰好构成一个树形网络。在树形网络上&#xff0c;任意两台电脑之间有唯一的路径相连。    不过在最近一次维护网络时&#xff0c;管理员误操作使得某两台电脑之间增…...

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 );实验一&#xff1a;分别往三张表插入 小数…...

Java封装最佳实践:打造高内聚、低耦合的优雅代码~

​ 个人主页&#xff1a;秋风起&#xff0c;再归来~ 文章专栏&#xff1a;javaSE的修炼之路 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 1、封装 1.1 封装的概念 面向对象程序三大…...

开源,微信小程序-超级计算器T3000 简介

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

Dimitra:基于区块链、AI 等前沿技术重塑传统农业

根据 2023 年联合国粮食及农业组织&#xff08;FAO&#xff09;、国际农业发展基金&#xff08;IFAD&#xff09;等组织联合发布的《世界粮食安全和营养状况》报告显示&#xff0c;目前全球约有 7.35 亿饥饿人口&#xff0c;远高于 2019 年的 6.13 亿&#xff0c;这意味着农业仍…...

降低项目延期概率的5大注意事项

降低项目延期概率对项目非常重要。因为项目延期往往会导致成本增加&#xff0c;降低客户满意度&#xff0c;影响企业在市场上的竞争力&#xff0c;造成资源浪费。因此&#xff0c;我们需要降低项目延期概率&#xff0c;实现企业长远发展。 而降低项目延期概率&#xff0c;一般来…...

在VUE页面调用Extjs中定义的方法

VUE版本&#xff1a;VUE2 EXTJS版本&#xff1a;4.2.6 1、在extjs页面上写监听事件&#xff08;主要利用了window.addEventListener来监听message事件 window.addEventListener("message", function(event) {// 这里写监听到消息后的逻辑&#xff0c;event.data就是…...

【独立开发前线】Vol.32 能够坚持下去的人并没有你想象的那么多

如果你有一个博客&#xff0c;你就已经超过了80%的独立开发者&#xff1b; 如果你每周更新自己的博客&#xff0c;你就已经超过了90%的独立开发者&#xff1b; 如果你每天更新自己的博客&#xff0c;你就已经超过了99%的独立开发者&#xff1b; 能够坚持下去的人并没有你想象…...

Java 扫描某包下所有类的注解并获得注解值

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

根据实例逐行分析NIO到底在做什么

Selector&#xff08;选择器&#xff09;是 Channel 的多路复用器&#xff0c;它可以同时监控多个 Channel 的 IO 状况&#xff0c;允许单个线程来操作多个 Channel。Channel在从Buffer中获取数据。 选择器、通道、缓冲池是NIO的核心组件。 一、新建选择器 此时选择器内只包含…...

TypeScript-对象的类型(接口)

1.接口 说明&#xff1a;TypeScript 中的接口&#xff08;Interfaces&#xff09;是一种用来定义对象的结构或者契约的方式。通过接口&#xff0c;你可以定义对象应该具有哪些属性、方法以及它们的类型。 2.一致性 说明&#xff1a;接口的属性名和对象的属性名必须一致性。 …...

Windows服务器安全策略配置几个步骤,轻松加强服务器安全

Windows服务器安全策略怎么做&#xff1f;不要觉得这是一个非常深奥遥不可及的问题&#xff0c;其实也是从各个方面去加固系统的安全性而已&#xff0c;它没有一个定论&#xff0c;今天德迅云安全就跟用户们分享一下windows服务器基本安全策略保障服务器基本安全的一些简单实用…...

Hive详解(2)

​​Hive 表结构 分区表 多字段分区&#xff1a;需要使用多个字段来进行分区&#xff0c;那么此时字段之间会构成多层目录&#xff0c;前一个字段形成的目录会包含后一个字段形成的目录&#xff0c;从而形成多级分类的效果。例如商品的大类-小类-子类&#xff0c; 省市县、年…...

【浅尝C++】STL第二弹=>迭代器失效详解/vector常用接口使用示例/vector底层结构探索/vector模拟实现代码详解

&#x1f3e0;专栏介绍&#xff1a;浅尝C专栏是用于记录C语法基础、STL及内存剖析等。 &#x1f3af;每日格言&#xff1a;每日努力一点点&#xff0c;技术变化看得见。 文章目录 vector介绍vector常用接口及使用示例构造类函数迭代器的使用容量操作增删改查 迭代器失效详解与v…...

【pytest】pytest` 中几种常用的参数化方法

pytest 是一个强大的 Python 测试框架&#xff0c;它提供了多种参数化测试的方法。参数化测试允许你使用不同的输入集来运行相同的测试逻辑&#xff0c;从而确保代码在各种条件下都能正常工作。以下是 pytest 中几种常用的参数化方法&#xff1a; 1. 使用 pytest.mark.paramet…...

设计模式-装饰者模式在Java中使用实例-打印发票装饰抬头和脚注

场景 设计模式-装饰者模式在Java中的使用示例&#xff1a; 设计模式-装饰者模式在Java中的使用示例_java装饰者模式例子-CSDN博客 上面装饰器的调用示例如下 AbstarctComputer computer;//要买1台电脑computer new BaseComputer();//加一个内存条computer new MemoryDecor…...

parallel linux虚拟机没有root权限

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

科技下乡:数字乡村改变乡村生活方式

在科技飞速发展的时代&#xff0c;数字化、信息化浪潮正以前所未有的速度席卷全球。在这场科技革命中&#xff0c;乡村不再是滞后的代名词&#xff0c;而是成为了数字乡村建设的热土。科技下乡&#xff0c;让数字乡村成为了改变乡村生活方式的重要力量。 一、科技下乡&#xf…...

【GitLab】Ubuntu使用宝塔安装GitLab最新社区版

首先在Ubuntu安装宝塔面板 在官网可以找到脚本一键安装 安装GitLab社区版 然后在宝塔面板的“软件商店”里面找到GitLab最新社区版 12.8.1一键安装 安装过程中可能出现以下问题&#xff1a; 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 引…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...