#216. 玉衡

    ID: 216 Type: Default 1000ms 256MiB Tried: 32 Accepted: 5 Difficulty: 8 Uploaded By: Tags>搜索并查集图论最短路2025寒假一期结训赛

玉衡

题目背景

在2023年第46届ICPC World Final世界总决赛的热身赛时,Jiangly的队伍非常不巧的连接不上网络,导致看不到热身赛题目,也无法提交代码。

赛后Jiangly向主办方反映了这个问题,发现不止这一队的网络有问题。

第二天就是正式赛了,如果在正式赛中再次出现这种问题,那么大赛承办方AASTMT就要颜面扫地了,甚至失去承办比赛资格。

由于把现场的124124个队伍都检查一遍需要非常多的时间,但好在他们有现场所有队伍和服务器的网线连接情况,现在需要你来帮他们检查有哪些队伍的电脑无法连接网络。

题目描述

已知现场共有nn支队伍,每个队伍都有一台电脑,编号为11nn,而00号电脑是AASTMT的服务器。

现在这些电脑通过一些网线进行了连接,数据通过网线是双向传输的,即若电脑aa与电脑bb之间有网线连接,则数据可以从aa到达bb,也可以从bb到达aa

如果一台电脑的数据可通过某条路径到达服务器(即00号电脑),则这台电脑可以连接到服务器。

现在你需要找到哪些电脑无法连接到服务器。

题目格式

输入格式

第一行输入两个整数n,m(1n105,0m105)n,m(1 \le n \le 10^5,0 \le m \le 10^5),表示有nn台电脑,连接了mm条网线,保证不会出现自己连接自己和重复连接的情况。

接下来mm行,每行输入两个整数ai,bi(0ain,0bin)a_i,b_i(0 \le a_i \le n,0 \le b_i \le n),表示有一条网线连接了两台电脑。

输出格式

输出一行由空格隔开的整数,表示连接不到网络的电脑的编号,从小到大输出。

如果所有电脑都可以连接到网络,则输出ALL CONNECTED

题目样例

3 2
0 1
1 2
3
8 9
0 1
0 2
1 3
2 3
4 6
5 6
6 7
6 8
7 8
4 5 6 7 8

题目声明

本故事纯属虚构,灵感取材自2024CCPC哈尔滨站