并查集

参考资料

• 并查集 - OI Wiki
• 并查集 - 维基百科

实现

struct DSU
{
	int fa[N];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
	void merge(int u,int v){fa[find(u)]=find(v);}
    bool query(int u,int v){return find(u)==find(v);}
}dsu;

例题

洛谷 P3367 【模板】并查集

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
int fa[N];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(int u,int v){fa[find(u)]=find(v);}
bool query(int u,int v){return find(u)==find(v);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	init(n);
	while(m--)
	{
		int z,x,y;
		cin>>z>>x>>y;
		if(z==1)merge(x,y);
		else if(z==2)cout<<(query(x,y)?'Y':'N')<<'\n';
	}
	return 0;
}

洛谷 P1525 [NOIP2010 提高组] 关押罪犯

#include <bits/stdc++.h>
using namespace std;

const int N=20005;
const int M=100005;
struct Node
{
	int u,v,w;
}a[M];
bool cmp(const Node &u,const Node &v)
{
	return u.w>v.w;
}
int fa[N<<1];
int find(int u)
{
	return u==fa[u]?u:fa[u]=find(fa[u]);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n<<1;i++)fa[i]=i;
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int x=a[i].u,y=a[i].v;
		if(find(x)==find(y)||find(x+n)==find(y+n))
		{
			ans=a[i].w;
			break;
		}
		fa[find(x)]=find(y+n);
		fa[find(x+n)]=find(y);
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P1892 [BOI2003] 团伙

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
int fa[N<<1];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(int u,int v){fa[find(v)]=find(u);}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=(n<<1);i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		char op;
		int p,q;
		cin>>op>>p>>q;
		if(op=='F')
		{
			merge(q,p);
		}
		else if(op=='E')
		{
			merge(p,q+n);
			merge(q,p+n);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i)ans++;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P2024 [NOI2001] 食物链

#include <bits/stdc++.h>
using namespace std;

const int N=50005;
int fa[N*3];
int find(int u){return u==fa[u]?u:u=find(fa[u]);}
void merge(int u,int v){fa[find(v)]=find(u);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n*3;i++)fa[i]=i;
	int ans=0;
	while(k--)
	{
		int op,u,v;
		cin>>op>>u>>v;
		if(u>n||v>n)
		{
			ans++;
			continue;
		}
		if(op==1)
		{
			if(find(u)==find(v+n)||find(u+n)==find(v))ans++;
			else
			{
				merge(u,v);
				merge(u+n,v+n);
				merge(u+n*2,v+n*2);
			}
		}
		else if(op==2)
		{
			if(find(u)==find(v)||find(u+n)==find(v))ans++;
			else
			{
				merge(u,v+n);
				merge(u+n,v+n*2);
				merge(u+n*2,v);
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}