上链接：P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
https://www.luogu.com.cn/problem/P1536
上题干：
题目描述
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？
输入格式
输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 n 和道路数目 m ；随后的 m 行对应 m 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 11 到 n 编号。
注意：两个城市间可以有多条道路相通。
在输入数据的最后，为一行一个整数 0，代表测试数据的结尾。
输出格式
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
输入输出样例
输入 #1复制
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0输出 #1复制
1 0 2 998说明/提示
数据规模与约定
对于 100%100% 的数据，保证1≤n<1000 。
这道题属于并查集的很好的练习题。
考察的内容有以下几点：
1，并查集模板（初始化父节点，查询祖先，连结两个集合）
2，理解题意
3，计算此时总共有几个集合。
这道题，无非就是上一道题洛谷P1551亲戚的换壳版。
详情可以看看我的这篇文章：
《洛谷深入浅出基础篇》P1551亲戚——集合——并查集P1551亲戚-CSDN博客https://blog.csdn.net/louisdlee/article/details/134427867?spm=1001.2014.3001.5502每两个城市之间连接一条道路，假设这两个城市为x，y。
连接x的城市一定和y是连通关系（毕竟可以通过x到达y）
连接y的城市一定和x是连通关系
现在让我们求还要修建多少条路使得所有城市被连通，
也就是算，我们当前一共有多少个不同的集合，每个集合之间只需要一条路就能连通。（一个孤立的城市也算一个集合）
即如果有三个集合，那么需要2条路就可以使之全部打通。
如果有n个集合，那么需要n-1条路就可以使之全部打通。
所以我们只需要求出集合的个数，然后输出集合-1就行了。
上代码：
const int N = 1e3+10;
int fa[N], flag[N];
int n, m;
int find1(int x)
{
if (fa[x] == x)return fa[x];
else return fa[x] = find1(fa[x]);
}
void join1(int c1, int c2)
{
int f1 = find1(c1), f2 = find1(c2);
if (f1 != f2) fa[f1] = f2;
}
int main()
{
while (cin >> n >> m)
{
memset(fa, 0, sizeof(fa));
memset(flag, 0, sizeof(flag));
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
join1(x, y);
}
int ans = 0;
for(int i=1;i<=n;i++)
for (int j = i; j <= n; j++)
if (find1(i) ==find1(j))flag[find1(i)] = 1;
for (int i = 1; i <= n; i++)
if (flag[i])ans++;
cout << ans-1 << endl;
}
}
