[数据结构与算法]从零开始的数据结构：种类并查集

众所周知并查集可以表示一些东西是否在一个集合里。

const int N = 2e6 + 10;
int fa[N],n;
void init(){for (int i = 1; i <= n; i++)fa[i] = i; }
int find(int x) { return fa[x] == x ? x:fa[x] = find(fa[x]); }
void merge(int a, int b) {if(find(a)!=find(b))fa[find(a)] = find(b); }

上面就是并查集所有的操作了。
但是我们有些时候不仅仅是要记录一些人是否是同一个阵营，而是要去表示分别属于哪几个阵营的话，普通并查集就比较难维护了。

来看一道例题：
落谷p2024

这道题要我们维护一堆动物的两种关系
总共有三个种类 分别为克制关系，题目一开始不知道这些动物到底属于哪一类，但是先出现的话会被当做真的，如果后面的不符合前面的当做假话就不记录关系。

1.A B是否为同一类动物。
2.A是否能吃B。

可以发现第一种关系普通的并查集就可以做到，但是第二种表示两种动物的对立关系好像就很难维护。

这个时候就可以用种类并查集。

种类并查集其实就是通过扩大我们所要的空间，来建立起更多的关系。

接下来我们假设A>B>C>A；
比如在这道题里面，要表示三种对立关系的话，我们就开三倍的空间，
我们分别把 $(1??n)(n+1??2?n)(2?n+1??3?n)$的空间来分别表示每个动物的关系A,B,C，一开始(1,n+1,2*n+1)都表示的是第一个动物，但是我们不知道关系，所以他就可能有三种身份。

对于第一种操作：我们就把3个并查集都合并就行了，和普通并查集一样，只是要做3次。
对于第二种操作：我们把A中的x与B中的y合并就表示x能吃y，同理合并的操作也做三次。

ps:我们在判断能否合并的时候要注意，如果x吃y，又出现了y吃z，应该是z吃x了，那么x吃z就是假话。所以我们不能只判断a b是否为同一类就判错.

丑陋的画图帮助理解
n为4的时候
初始状态：

第一种操作：2和3连接

第二种操作：3吃4

此时我们在说4吃2的话就不行，因为4已经和克制他阵营的2在一个集合里（即2吃4）

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 2e5 + 10;
const int N = 5e4 + 10;
int n,m;
int fa[N*3];
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void work() 
{
	cin>>n>>m;
	for(int i=1;i<=3*n;i++)
	{
		fa[i]=i;
	}
	int ans=0;
	while(m--)
	{
		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)==find(v+2*n))//u能吃v||v能吃u
			{
				ans++;
			}
			else
			{
				fa[find(u)]=find(v);
				fa[find(u+n)]=find(v+n);
				fa[find(u+n*2)]=find(v+2*n);
			} 
		}
		else
		{
			if(find(u)==find(v)||find(u+n)==find(v))//u,v同类||v能吃u
			{
				ans++;
			}
			else
			{
				fa[find(u)]=find(v+n);
				fa[find(u+n)]=find(v+2*n);
				fa[find(u+2*n)]=find(v);
			}
		} 
	}
	cout<<ans<<endl;
}
int main() {
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 
	int t = 1;//忽略这里，多组样例的题用的
	//cin >> t;
	while (t--)work();
	return 0;
}

其他的例题
落谷p1525