并查集

⬅ 返回

1、思路

用一个数组f[]记录每个元素的父节点，初始时f[i]=i，自己是老大。

若要将元素a所在的集合与元素b所在的集合合并：

2、例题

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b，将编号为 和 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 和 的两个数是否在同一个集合中；

3、代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int f[N];//查找父节点 
-----------------------------------------------------------------------------
//路径优化的写法
int find_root(int x)
{
	if(f[x]!=x){  //此处采用了递归的写法
	    f[x] = find_root(f[x]);//路径优化的关键 令x的父亲直接为祖宗节点（根结点）
	}
	return f[x];
} 
------------------------------------------------------------------------------
//正常写法
int find_root(int x)
{
	while(f[x]!=x)//直到x的父亲是x时 才算找到祖宗结点（根节点）
	{
		x=f[x];
	}
	return f[x];
} 
----------------------------------------------------------------------------
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	while(m--)
	{
		char c;
		int a,b;
		cin>>c>>a>>b;
		int r1 = find_root(a);
		int r2 = find_root(b);
		
		if(c=='M')
		{
			f[r1]=r2;
			
		}else if(c=='Q')
		{
			if(r1==r2)
				cout<<"Yes"<<endl;
			else 
				cout<<"No"<<endl;
		}
----------------------------------------------------------------------------
	} 
	
	
	
	
	
	
}