并查集与反集——P1892团伙

并查集

并查集如其名，合并与查找

• 查找

int find(int key)
{
	if(fa[key]==key) return key;
	else return fa[key]=find(fa[key]);
}

• 合并

void unite(int x, int y) {
	int fax = find(x);
	int fay = find(y);
	fa[fax] = fay;
	return ;
}

反集

处理并查集合并问题的敌对/朋友关系的一种集合

如此时有两个人，吉吉和毛毛，那么两人根据题意只有两种关系，朋友或者敌人（不考虑两人是陌生人），那么根据这两种关系

1. 两人是朋友时
   合并吉吉与毛毛，并且合并吉吉的敌人和毛毛的敌人
2. 两人是敌人时
   合并吉吉与毛毛的敌人，合并毛毛与吉吉的敌人

如何实现这一问题？

定义一个数组 \(fa[2*n],1-n\) 表示朋友关系,\(n+1-2n\) 表示敌人关系

\(unite(吉吉，毛毛),unite(吉吉的敌人，毛毛的敌人)\)

\(unite(吉吉的敌人，毛毛)，unite(毛毛的敌人，吉吉)\)

到此为止做这道题目的前置知识已经具备，分析题目的意思，我们并不能知道敌人的朋友就是敌人，或者朋友的敌人就是敌人，所以不需要合并朋友的敌人，即为此步骤\(unite(吉吉的敌人，毛毛的敌人)\)不用进行。

\(code\)：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int fa[maxn*2];
int n,m;
int find(int key)
{
	if(fa[key]==key) return key;
	else return fa[key]=find(fa[key]);
}
void unite(int x, int y) {
	int fax = find(x);
	int fay = find(y);
	fa[fax] = fay;
	return ;
}
int main() {
	cin>>n>>m;
	for (int i=1;i<=2*n;i++) fa[i]=i;
	for (int i=1;i<=m;i++){
		char op;
		int p,q;
		cin>>op>>p>>q;
		if(op=='F') unite(p,q);
		else if(op=='E') {
			unite(p+n,q);
			unite(q+n,p);
		}
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		if(find(i)==i)
			ans++;
	printf("%d\n", ans);
	return 0;
}

P2024这道题目和这个有相似之处，感兴趣的同学可以尝试一下