并查集
并查集是一种维护集合的数据结构，有两个操作：
1.合并：合并两个集合
2.查找：判断两个元素是否在一个集合
实现
father[i]表示i的父亲结点，如果father[i]=i,则说明元素i是该集合的根节点，一个集合只有一个根节点，且将其作为所属集合的标识。
基本操作
- 初始化：一开始每个元素都是一个独立的集合
for(int i = 1; i <= n; i++) {
father[i] = i;
}
2.查找
int findFather(int x){//找根结点
while(x!=father[x]){
x=father[x];
}
return x;
}
3.合并
void Union(int a,int b){
int fa=findFather(a);
int fb=findFather(b);
if(fa!=fb){
father[fa]=fb;
}
}
4.完整实现
#include<cstdio>
int father[100];
bool isRoot[100];
void init(int n);
int findFather(int x);
void Union(int a,int b);
int main(){
int n,m,a,b;//n:结点个数,m:组数
scanf("%d%d",&n,&m);
init(n);//把每个结点看成一个独立的集合和根结点
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
Union(a,b);
}
for(int i=1;i<=n;++i){
int j=findFather(i);
isRoot[j]=true;
}
int k=0;
for(int i=1;i<=n;++i){
if(isRoot[i]==true)
k++;
}
printf("%d",k);
return 0;
}
void init(int n){
for(int i=1;i<=n;++i){
father[i]=i;
isRoot[i]=false;
}
}
int findFather(int x){//找根结点
while(x!=father[x]){
x=father[x];
}
return x;
}
void Union(int a,int b){
int fa=findFather(a);
int fb=findFather(b);
if(fa!=fb){
father[fa]=fb;
}
}
