原题链接:https://www.luogu.com.cn/problem/P1536
题意解读:城镇之间现有的道路关系可以将城镇划分的若干集合,每个集合内的城镇是互通的,要计算最少增加多少条道路,使得每个集合都相通。
解题思路:
利用并查集,统计一共出现多少个集合,即p[i] = i的数量,
最少的道路数即集合数-1,即可把所有集合“串”起来,使得所有城镇可以互通。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int p[N], n, m;
int find(int x)
{
if(p[x] == x) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y)
{
p[find(x)] = find(y);
}
int main()
{
int i, j;
while(cin >> n && n != 0)
{
cin >> m;
for(int i = 1; i <= n; i++) p[i] = i; //多组数据,每次都要对并查集初始化
while(m--)
{
cin >> i >> j;
merge(i, j);
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(p[i] == i) ans++; //p[i] = i的即根节点,也就是集合的编号
}
cout << ans - 1 << endl;
}
return 0;
}
标签:P1536,return,int,洛谷题,城镇,集合,find,村村通 From: https://www.cnblogs.com/jcwy/p/18084906