并查集

并查集的定义和实现思路

并查集是一种维护集合类型的数据结构，它的名字中“并”“查”“集”分别取自union(合并)、find(查找)、set(集合)这三个单词。也就是说并查集支持下面的操作：

• 合并：对两个集合进行合并。
• 查找：判断两个元素是否为在一个集合。
  具体实现：用数组father[N]来实现
  
  其中father[i]表示元素i的父亲结点，父亲结点本身也是这个集合内的元素(1<=i<=N)。但是对于同一个集合来说只存在一个根结点，而且将其作为所诉集合的标识。
  例如：
  father[1]=1;//1的父亲就是自己，也就是说1是根节点
  father[2]=1;//2的父亲结点是1
  father[3]=1;//3的父亲结点是1
  father[4]=1;//4的父亲结点是1
  father[5]=4;//5的父亲结点是4
  father[6]=4;//6的父亲结点是4
  上述情况元素1-6都在同一个及格

2.并查集的基本操作

• 初始化
  在一开始每一个元素都是独立的一个集合，因此要令所有的father[N]等于i。

for(int i=1;i<=n;i++){
   //初始化不能忘记，注意让i=1
	father[i]=i;
}

• 查找
  反复寻找父亲结点直至找到根节点

int find(int x){
   
	if(x==father[x]) return x;//直接找到了根节点
} else {
   
	int t=find(father[x]);//递归找到father[x]的根节点
	father[x]=t;//找到自己的父亲结点
	return t;
}

• 合并
  合并一般是给出两个元素，把这两个元素所在集合合并(若给出多个元素要有所处理)

int ufs(int a,int b){
   
	int t1=find(a);
	int t2=find(b);
	if(t1!=t2){
   
		father[t1]=t2;
	}
}

注意如果一行给出多个元素需要读入，一般拿出来第一个元素出循环进行读入
直接给出代码：

for(int j=1;j<=m;j++){
   
	cin>>a;
for(int i=1;i<=n-1;i++){
   
	cin>>b;
	ufs(a,b);//以两个两个一合并来遍历每一行
	}
}

3.并查集的实例

输入样例:

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例:

4

这是一道并查集运用的题目，我们按照前文所讲给出代码：

#include<bits/stdc++.h>
using namespace std;
int num[30005];
int cn[30005];
int find(int x){
   //查找模块 
	if(num[x]==x) return x;
	else {
   
		int t=find(num[x]);
		num[x]=t;
		return t;
	}
}
void ufs(int e,int f){
   //合并模块 
	int t1=find(e);
	int t2=find(f);
	if(t1!=t2) num[t1]=t2;
}
int main(){
   
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++) num[i]=i;
	int a,b,c,d;
	while(n--){
    
		cin>>a;
		cin>>b;
		for(int i=1;i<=a-1;i++){
   
			cin>>c;
			ufs(b,c);
		}
	}
	for(int i=1;i<=m;i++){
    //对集合个数进行技术 
		cn[find(i)]++;
	}
	int max=0;//找出最大值 
	for(int i=1;i<=m;i++){
   
		if(cn[i]>max) max=cn[i];
	}
	cout<<max<<endl;
	return 0;
} 

总结：并查集这种算法很常见，读者可以将并 查两个模板进行理解记忆，对后面的处理多多写题就可以理解，常见的基础类型就是并集集合个数、并集集合元素等等问题，一定要自己亲自敲几遍代码就可以理解。