并查集

比眉伴天荒 2021-06-22 15:37 537阅读 0赞

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并

基本模板

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1e5+10;

int n,m;
    int f[maxn];// 当前节点的父节点

int find(int x){ //路径压缩的写法 ，返回的该节点的祖宗节点
    	if(x!=f[x]){ //如果一个点的父亲节点是本身就说明 
    		f[x]=find(f[x]);
    	}
    	//查找x所在集合的祖先节点下标，将x的父亲节点指向祖先节点 
    	return f[x];
    }

int main(){ 
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){ 
    		f[i]=i;//首先将每个节点的父亲初始化为自己本身，自己是一个集合 
    	}
    	char c;
    	while(m--){ 
    		cin>>c;
    		int a,b;
    		if(c=='M'){ 
    		   cin>>a>>b;
    		   int fa=find(a);
    		   int fb=find(b);
    		   if(fa!=fb){ //如果a和b不是同一个集合 
    		   	  f[fa]=fb;//将a的祖先节点的父亲指向b的祖先节点 
    		   }
    			
    		}
    		else if(c=='Q'){ 
    		   cin>>a>>b;
    		  int fa=find(a);
    		   int fb=find(b);
    		   if(fa==fb){ //如果祖先节点相同说明在一个集合中 
    		   	cout<<"Yes"<<endl;
    		   }
    		   else{ 
    		   	cout<<"No"<<endl;
    		   }
    		}
    	}
    	
    	
    	return 0;
    }

应用求每个集合的数量，只需要维护的是祖先节点的数量代表整个集合的数量即可

给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
    
    现在要进行m个操作，操作共有三种：
    
    “C a b”，在点a和点b之间连一条边，a和b可能相等；
    “Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
    “Q2 a”，询问点a所在连通块中点的数量；
    输入格式
    第一行输入整数n和m。
    
    接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。
    
    输出格式
    对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。
    
    对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量
    
    每个结果占一行。
    
    数据范围
    1≤n,m≤105
    输入样例：
    5 5
    C 1 2
    Q1 1 2
    Q2 1
    C 2 5
    Q2 5
    输出样例：
    Yes
    2
    3

#include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;
    const int maxn=1e5+10;

int n,m;
    int f[maxn];// 当前节点的父节点
    int cnt[maxn];//统计集合内元素的数量

int find(int x){ //路径压缩的写法 
    	if(x!=f[x]){ //如果一个点的父亲节点是本身就说明 
    		f[x]=find(f[x]);
    	}
    	//查找x所在集合的祖先节点下标，将x的父亲节点指向祖先节点 
    	return f[x];
    }

int main(){ 
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){ 
    		f[i]=i;
    		cnt[i]=1;//首先将每个节点的父亲初始化为自己本身，自己是一个集合 
    	}
    	string op;
    	while(m--){ 
    		cin>>op;
    		int a,b;
    		if(op=="C"){ 
    		   cin>>a>>b;
    		   int fa=find(a);
    		   int fb=find(b);
    		   if(fa!=fb){ //如果a和b不是同一个集合 
    		       cnt[fb]+=cnt[fa];
    		   	  f[fa]=fb;//将a的祖先节点的父亲指向b的祖先节点 
    		   }
    			
    		}
    		else if(op=="Q1"){ 
    		   cin>>a>>b;
    		  int fa=find(a);
    		   int fb=find(b);
    		   if(fa==fb){ //如果祖先节点相同说明在一个集合中 
    		   	cout<<"Yes"<<endl;
    		   }
    		   else{ 
    		   	cout<<"No"<<endl;
    		   }
    		}
    		else if(op=="Q2"){ 
    			int a;
    			cin>>a;
    			cout<<cnt[find(a)]<<endl;
    		}
    	}
    	
    	
    	return 0;
    }