并查集

参考资料

实现

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);}
};

例题

洛谷 P3367 【模板】并查集

如题，现在有一个并查集，你需要完成合并和查询操作。

Code (1)

#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 [NOIP 2010 提高组] 关押罪犯

S 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1\sim N$ 。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用「怨气值」（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

Code (1)

#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 [BalticOI 2003] 团伙

现在有 $n$ 个人，他们之间有两种关系：朋友和敌人。我们知道：

一个人的朋友的朋友是朋友
一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

Code (1)

#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] 食物链

动物王国中有三类动物 $A,B,C$ ，这三类动物的食物链构成了有趣的环形。 $A$ 吃 $B$ ， $B$ 吃 $C$ ， $C$ 吃 $A$ 。

现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
第二种说法是 2 X Y，表示 $X$ 吃 $Y$ 。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

当前的话与前面的某些真的话冲突，就是假话；
当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
当前的话表示 $X$ 吃 $X$ ，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

Code (1)

#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;
}

参考资料​

实现​

例题​

参考资料

实现

例题