54-蓝桥侦探（蓝桥杯）
创始人
2025-05-31 16:29:20

题目描述

小明是蓝桥王国的侦探。

这天，他接收到一个任务，任务的名字叫分辨是非，具体如下：

蓝桥皇宫的国宝被人偷了，犯罪嫌疑人锁定在 N 个大臣之中，他们的编号分别为 1∼N。

在案发时这 N 个大臣要么在大厅1，要么在大厅2，但具体在哪个大厅他们也不记得了。

审讯完他们之后，小明把他们的提供的信息按顺序记了下来，一共 M 条，形式如下：

  • x y，表示大臣 x 提供的信息，信息内容为：案发时他和大臣 y 不在一个大厅。

小明喜欢按顺序读信息，他会根据信息内容尽可能对案发时大臣的位置进行编排。

他推理得出第一个与先前信息产生矛盾的信息提出者就是偷窃者，但推理的过程已经耗费了他全部的脑力，他筋疲力尽的睡了过去。作为他的侦探助手，请你帮助他找出偷窃者！

输入描述

第 11 行包含两个正整数 N,M，分别表示大臣的数量和口供的数量。

之后的第 2∼M+1 行每行输入两个整数 x,y，表示口供的信息。

1≤N,M≤5×105，1≤x,y≤N。

输出描述

输出仅一行，包含一个正整数，表示偷窃者的编号。

输入输出样例

示例 1

输入
4 5 
1 2
1 3 
2 3 
3 4
1 4
输出
2

运行限制

  • 最大运行时间：1s

  • 最大运行内存: 256M

源码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class 蓝桥侦探 {static class UnionFind{int[] parent;int[] rank;public UnionFind(int n) {parent=new int[n];for (int i = 0; i < n; i++) {parent[i]=i;}rank=new int[n];Arrays.fill(rank, 1);}public int find(int ind) {if(parent[ind]!=ind) parent[ind]=find(parent[ind]);return parent[ind];}public void unite(int ind1,int ind2) {int root1=find(ind1),root2=find(ind2);if (root1!=root2) {if (rank[root1]
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：ChatGPT能否取代程序员？

下一篇：全球豪车市场，迎来中国时刻！ 全球豪车价格暴跌 中国豪车市场近十年回顾

相关内容

热门资讯

增长53%！1至4月雄安民营企... 河北日报客户端讯（康晓博、王敏）从雄安海关获悉，今年1至4月，雄安新区进出口总值14.7亿元，同比增...
深圳华大智造科技股份有限公司关... 本公司董事会及全体董事保证本公告内容不存在任何虚假记载、误导性陈述或者重大遗漏，并对其内容的真实性、...
金价狂飙，金表也不好卖了 泡泡玛特、老铺黄金、蜜雪冰城股价屡创新高，被港股市场称为“新消费三姐妹”。与它们有着异曲同工之妙的金...
汉口银行拟吸收业绩下滑资产，谋... 文 | 刘振涛谋求IPO的汉口银行，拟吸收合并村镇银行，谋划异地扩张。近日，汉口银行发布公告，将在6...
孩子疯玩，成绩疯涨，有可能吗？...
大连银行迎新帅 能否走出“消失... “ 过去十年，大连银行业绩可谓是原地踏步，2018年到2023年，净利润更是六连降。去年，大连银行结...
雷军凶猛，兵临董明珠城下 雷军... 家电大战，全面开打。文 | 华商韬略 东木褚小米的大家电业务爆发了，营收首次突破1000亿大关。去年...
财报里的十大跨境巨头：出海增长... 作者 | 唐飞编辑 | 谭格2024年的跨境电商江湖，正经历着前所未有的冰火两重天。一边是安克创新靠...
A股、港股云计算概念双双走强，... 6月5日，三大指数集体高开，盘中创业板指走高，港股方面，恒生科技指数涨幅走阔。A股、港股云计算概念双...
财报解读｜蔚来一季度营收增长2... 21世纪经济报道记者 郑植文 上海报道6月3日，蔚来汽车发布了2025年第一季度财报。数据显示，20...
广发基金王明旭：面对市场逆风，... （来源：资事堂）过去五年里，我们对话了数百名基金经理，广发基金王明旭无疑是极具特点且与众不同的。第一...
小商品城股价创历史新高 小商品... 6月5日，小商品城股价振荡上扬，最高涨至18.99元/股，创下历史新高。截至记者发稿，公司市值达10...
张裕A被调出深证成指，总经理孙... 瑞财经 刘治颖 6月3日，深交所发布公告称，将于6月16日对深证成指、创业板指、深证100等指数实施...
信音电子：6月4日融资买入26... 证券之星消息，6月4日，信音电子（301329）融资买入268.8万元，融资偿还146.89万元，融...
李斌：蔚来正在走出最低谷，二季... 成立11年，蔚来遭遇多次起伏。 2019年时，蔚来靠外部融资成功复活；而今年一季度，在外部唱衰之下，...
海科新源：6月4日融资买入38... 证券之星消息，6月4日，海科新源（301292）融资买入381.85万元，融资偿还265.17万元，...
长安、东风重组中止 兵装集团汽... 经观要闻 经过116天的磋商与谈判之后，两大汽车央企东风与长安的重组计划中止。 长安汽车（0006...
“苏超”引爆A股足球概念持续狂... 6月5日早盘，足球概念再度走强，截至发稿，金陵体育、共创草坪涨停，星辉娱乐涨超9%，探路者、康力源、...
人工智能产业迎政策利好，恒生互... 6月5日早盘，港股集体走强。截至发稿，恒生互联网科技业指数涨2.38%，微盟集团涨超6%，快手-W、...
商业航天概念股爆发，超捷股份超... 6月5日，商业航天概念股爆发，超捷股份超逾15%，天银机电、上海瀚讯、航宇微涨逾3%。
「开盘」A股三大股指集体小幅高... A股三大股指6月5日集体小幅高开。其中，沪指涨0.06%报3378.22点，深成指涨0.08%报10...
长安与东风不再合并，兵器装备集... 红星资本局6月5日消息，今日早间，长安汽车（000625.SZ）、中光学（002189.SZ）、湖南...
CRO概念股走低，金凯生科跌逾... 6月5日，CRO概念股走低，金凯生科跌逾8%，鸿博医药、泰格医药、成都先导、昭衍新药跌逾2%。
体育概念再度活跃，共创草坪四连... 6月5日，体育概念再度活跃，共创草坪四连板，冰山冷热、元隆雅图快速拉升涨停，金陵体育冲击涨停。
6月5日投资避雷针：7天5板人... 导读：财联社6月5日投资避雷针，近日，A股及海外市场潜在风险事件如下。国内经济信息方面包括：1）本周...
楼市已经触底，明年会回暖吗？国... 我最近一直在研究房地产市场，发现2024年的数据确实挺吓人的： 全国新建商品房销售面积同比下降12....
百亿市值大族数控冲击IPO：5... 瑞财经 王敏 5月30日，据港交所官网，深圳市大族数控科技股份有限公司（以下简称“大族数控”）向港交...
李在明上台，韩国转机将至？ 李... 6月4日上午11时许，韩国新任总统李在明在国会正式宣誓就职，开启五年任期。李在明在就职讲话中表示，将...
恒指高开0.74% 恒指高开0... 【恒指高开0.74%】香港恒生指数高开0.74%，恒生科技指数高开0.97%。蔚来涨超3%，阿里巴巴...
V观财报｜温氏股份实控人调整，... 　　中新经纬6月5日电 温氏股份4日晚间公告，公司的实际控制人自2025年6月4日起调整为温鹏程、温...