并查集
看的很好的博文
链接如下
https://blog.csdn.net/chen134225/article/details/82052537
两个函数
1.查找
int pre[1000];
int find(int x)//查找x的顶级
{
int r = x;
while (pre[r] != r)//当r的上级是他自己,那么r就是顶级
{
r = pre[r];
return r;
}
}
2.合并
void join(int x,int y)
{
int fx = find(x),fy = find(y);//找到两人的顶级
if(fx != fy)
pre[fx] = fy;// 如果两人的顶级不相等,那么一个人做上级,一个人做下级
}
相当于计算连通分支
如果1 和 2相连 2和3相连那么1 2 3相连
相当是划分集合的样子 都变为了树结构 应该后面还会有优化 等做到题再说吧
练习 hdu1232
链接如下
http://acm.hdu.edu.cn/showproblem.php?pid=1232
解题思路-并查集
先进行查找-合并 把相连通的连接到一起,计算有多少个连通分支,连通分支-1 即所需要的连接数。
代码如下
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int pre[1005];
void Init(int n) {
for(int i = 1; i<= n; i++) {
pre[i] = i;
}
}
int find(int x) {
while(pre[x] != x) {
x = pre[x];
}
return x;
}
void join(int a,int b) {
int temp_a = find(a),temp_b = find(b);
if(temp_a != temp_b) {
pre[temp_a] = temp_b;
}
}
//确定连通分量
int find_ans(int n) {
int sum = 0;
for(int i = 1; i <=n; i++) {
if(pre[i] == i)
sum++;
}
return sum;
}
int main() {
int n,m,a,b;
while(scanf("%d",&n)!=EOF) {
if(!n) break;
Init(n);
scanf("%d",&m);
for(int i = 0; i < m; i++) {
cin>>a>>b;
join(a,b);
}
cout<<find_ans(n)-1<<'\n';
}
return 0;
}