某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $139$ | 正确数量 | $62$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 图论 并查集 |
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。
对每个测试用例，在1行里输出最少还需要建设的道路数目。
5 3
1 2
3 2
4 5
0
1
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$0 $ms] | regex | 762846 | 2021-09-14 17:24:15 |
| 内存最少[$948 $KB] | 范晋豪@信息与计算科学142 | 152848 | 2017-11-16 15:10:19 |
| 第一AC | 范晋豪@信息与计算科学142 | 152847 | 2017-11-16 15:10:19 |
| 第一挑战 | 范晋豪@信息与计算科学142 | 152847 | 2017-11-16 15:10:19 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1656 | 2021-2022-1学期<算法分析与设计> 期初补考试练习赛 | 2021-09-05 00:00:00 | 请登录 |
| 1619 | 2020-2021-2学期<算法分析与设计ZJ28104> 期末考试【19计算机12】正式考试 | 2021-07-08 10:00:00 | 请登录 |