P1536 村村通

难度： 普及/提高−
算法标签： 并查集、连通块、图论
来源： 洛谷 P1536

题目背景

本题围绕“村村通”所描述的场景展开。某市有若干城镇，现有道路均为双向道路。

下面的题面采用非逐字重述方式整理，但保留原题中的全部判定条件、边界含义、输入输出要求与特殊约定。

某市有若干城镇，现有道路均为双向道路。工程目标是让任意两个城镇之间都能通过若干条道路互相到达。对于每组道路统计，请计算最少还需新建多少条道路才能实现全市连通。两个城镇之间允许已有多条重复道路。

处理本题时，必须同时满足下列全部要求，不能只实现其中一部分：

程序应完整读取“输入格式”中规定的所有数据，并严格按照“输出格式”给出结果。题目中的区间端点、编号起点、排序优先级、同分处理、空结构处理、取模方式和特殊字符串，均以本题面明确写出的规则为准。

所有算法还必须覆盖“数据范围”中的最小规模、最大规模及边界情况，不能只针对样例或小数据。

输入包含多组数据。每组第一行两个正整数 $n,m$ ，表示城镇数和现有道路数；接下来 $m$ 行每行两个整数，表示一条道路连接的两个城镇。城镇编号为 $1$ 到 $n$ 。最后单独一行 0 表示输入结束。

每组数据输出一行一个整数，表示最少需要新增的道路数。

1
0
2

样例输入按照上述规则处理。某市有若干城镇，现有道路均为双向道路。最终得到题面所列的样例输出。样例只用于说明规则与格式，程序仍需覆盖全部数据范围。

$1\le n<1000$ ；道路端点均在 $[1,n]$ ；可能存在重边。

本题面依据洛谷 P1536 的公开题目信息重新整理，为内容完整的非逐字重述版。