主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem B: 连接电脑
上一题
正确率: $59.49\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$512$ 兆字节/Megabyte(s)
提交总数
$1597$
正确数量
$950$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
图论
并查集
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
图论
并查集
单击选择分类:
Description
机房里有若干台电脑,其中有一些电脑已经相互连接。如果A和B通过网线相连,并且B与C也通过网线相连,那么即便A和C之间没有直接的网线相连,也可以认为A和C是相连的。由于机房里的布线比较乱,并不是所有电脑都相互连通,请问在不变动当前布线情况下,最少要购买几条网线才能使得机房所有电脑都两两连通。 <br />
Input
多组数据。每组数据第一行为整数N,M。N是电脑数量,M是机房已布置好的网线数量。接下来M行,每行为整数A,B。表明电脑A,B之间通过一条网线直接相连。这里可以认为网线是不分方向的,即A->B等价于B->A。 <br /> (0 < N <= 200,0 <= M <= 10000,1 <= A,B <= N 。) N=0和M=0为输入结束,不需要处理。
Output
每组一个整数,即最少还要购买几根网线。
Sample Input
复制
4 2 1 2 2 3 4 0 1 0 0 0
Sample Output
复制
1 3 0
提示
n个电脑编号为1~n
AOJ
Please Login