并查集.md

#内容 并查集主要用于统计多个元素的集合分属关系并统计互不相交的集合的总数。

简而言之，对于一个给定的初始集合，规定每个集合的根节点为自己，然后依次赋给每个根节点最后的要求节点，其中遍历的时候依据是看每个节点的根节点是否为自己，如果是则停止递归，表示找到了根节点；如果没有则继续递归，直到找到了根节点。

并查集能实现的操作有：将两个集合合并，或者查询两个元素是否在一个集合当中

实现代码： `# include using namespace std; void find(int x) { if(x!=s[x]) { return find(s[x]); } return x; }

void merge(int x,int y) //合并两个节点 { x=find(x); y=find(y); if(x!=y) s[x]=s[y]; } int main (void) { }

#路径压缩 如果在find根节点的时候就可以直接把根节点下的叶子节点全部改成直系叶节点，那么下次遍历的时候复杂度会将至0（1）.

代码修改简单。

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,p;
ll arr[5005];
ll find(ll x)
{
	if(arr[x]!=x)
	arr[x]=find(arr[x]);     //arr指的是对应的x的父亲，不一定是祖宗，但是经过路径压缩之后就是祖宗
	return arr[x];
	
}
void merge(ll a,ll b)
{
	if(find(a)==find(b))
	return ;
	else
	{
		arr[find(a)]=find(b);   //如果不一样，则令对方的祖宗为这边的祖宗
	}
}


int main (void)
{
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
	arr[i]=i;
	while(m--)
	{
		ll a,b;
		cin>>a>>b;
		merge(a,b);
		
		}
		while(p--)
		{
			ll x,y;
			cin>>x>>y;
			if(find(x)==find(y))
			cout<<"Yes"<<endl;
			else
			cout<<"No"<<endl;
			
			}	
	
}