首页 > 代码库 > 并查集的基本运用 POJ1611
并查集的基本运用 POJ1611
用并查集的情况是在比如 A和B联通 B和C联通那么 ABC联通 这类情况下算某个元素所在集合的元素个数。.
并查集数据结构用数组就行,数组的下标表示相应的一个主体,对应的值表示它的父节点的索引,指向父节点。根节点的值特殊一下就行;
原理:先把所有结点(元素)看成独立的集合,然后按给的条件来合并,合并的过程就是最重要的,结合已知条件,因为并查集是用于A和B联通 B和C联通那么 ABC联通 这类情况下算某个元素所在集合的元素个数 所以合并过程是把2个元素所在集合合并,实际情况就是比如已知AC合在一个集合了A为代表元素 后面跟着是DLK这个集合代表元素为D与C集合合并 那么合并函数应该具有的功能就是找到C元素所在集合的代表元素然后判断哪个集合大,大集合指向小集合(这是缩短树高减小查询次数,还有压缩路径可以优化时间),那么新集合变为DLKAC,是想要的结果。按这个来写合并函数,后来就会需要findroot函数等。 代码如下 POJ1611
#include <iostream>
int p[300001];//值是对应下标的父节点的下标
int num[300001];
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int set(int x){
p[x]=x;
num[x]=1;
return 0;
}
int findroot(int x){
int t=x;
while(p[x]!=x) x=p[x];
while(p[x]!=x){
x=p[x];
p[x]=t;
}//路径压缩;
return x;
}
int hb(int a,int b){
int t=findroot(a);
int s=findroot(b);
if(t!=s){
if(num[t]>=num[s]){
p[s]=t;
num[t]+=num[s];
}else{
p[t]=s;
num[s]+=num[t];
}
}
return 0;
}
int main() {
int n,m,k,a,b;
while(~scanf("%d %d",&n,&m),(n!=0||m!=0)){
for(int z=0;z<=n-1;z++){
set(z);
}
while(m--){
scanf("%d",&k);
scanf("%d",&a);
for(int i=1;i<=k-1;i++){
scanf("%d",&b);
hb(a,b);
}
}
printf("%d\n",num[findroot(0)]);
}
return 0;
}
并查集的基本运用 POJ1611