并查集：动态连通性

算法理解

并查集把每个连通块看成一棵树，根节点代表整个集合。find 在寻找根的同时进行路径压缩，之后再次查找会非常快。

• 适用：连通性判断、Kruskal、集合合并。
• 复杂度：路径压缩后均摊接近 O(1)。
• 注意：再加按大小/秩合并，极端数据会更稳定。

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int f[maxn];
void init(int n)
{
	for (int i=1;i<=n;i++)
	{
		f[i]=i;
	}
}
int find(int x)
{
	if (x==f[x]) return x;
	else return f[x]=find(f[x]);
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if (fx==fy)
	{
		return ;
	}
	else 
	{
		f[fx]=fy;
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	init(n);
	for (int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	int x,y;
	cin>>x>>y;
	if (find(x)==find(y))
	{
		cout<<"YES";
	}
	else
	{
		cout<<"NO";
	}
	return 0;
}