题目链接：P1536 村村通 - 洛谷 | 计算机科学教育新生态
题目难度：普及/提高
解题思路：本题很明显考察是并查集，并查集之前我的博客介绍过可以看看这篇 洛谷P1551 亲戚（c嘎嘎）-CSDN博客，本题是输入两个城市后就将他们连起来，用ans来记录需要建设的道路数目，然后遍历所有城市如果p[i] = i 的话，ans ++，最后输出ans - 1（因为三个城市仅需两条道路即可）
下面奉上AC代码：
#include<bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a); i<(b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll;
const int N = 1010;
int p[N];//存储每个点的祖宗节点
int n,m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int read()//快读函数
{
int k=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
k=k*10+ch-'0';
ch=getchar();
}
return k*f;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(nullptr),cout.tie(nullptr);
while(true)
{
n = read();
if(n == 0) return 0;
m = read();
for(int i=1; i<=n; i++) p[i] = i;//初始化自己的父亲是自己
while(m--)
{
int c1,c2;
c1 =read(),c2 = read();
p[find(c1)] = find(c2);//合并
}
int ans = 0;//ans要在循环中定义为0
for(int i=1; i<=n; i++)
{
if(find(i) == i) ans ++;
}
cout<<ans - 1<<'\n';
}
return 0;
}