概念

一.什么是种类并查集？

顾名思义就是把一个集合中的元素根据他们不同的关系进行分类与合并。朋友的朋友就是朋友（普通并查集） ，但敌人的敌人也是朋友（维护这种关系就是种类并查集了）。例如：有一伙人他们要拔河（分成两个队），如果小a与小b是敌对关系，那么就不能在一个队，如果小a与小c是朋友，那么他们就在一个队；(朋友的朋友就是朋友，敌人的敌人也是朋友。 ) 种类并查集的作用就是不让两个有敌对关系的人在同一个队伍

二.种类并查集的应用

把朋友放在同一集合里，把敌人放另一集合里。放一起会打架 开两倍pre数组，一倍放朋友，二倍放敌人。 如果关系再多点那就再开大点呗。

例题

经典例题[食物链](https://www.luogu.com.cn/problem/P2024)~~也可以用带权并查集做~~ 
动物王国中有三类动物 A,B,C，这三类动物的**食物链构成了有趣的环形**。**A 吃 B，B 吃 C，C 吃 A**。

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

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

**第一种说法是 1 X Y，表示 X 和 Y 是同类**。//分类条件1
**第二种说法是2 X Y，表示 X 吃 Y** 。//分类条件2
此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1.当前的话与前面的某些真的话冲突，就是假话//判断条件 2.当前的话中 X 或 Y 比 N 大，就是假话 3.当前的话表示 X 吃 X，就是假话 你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

一.解题思路如下：

1.根据题意我们要维护三种关系（同类，食物，天敌），这时三种关系普通的并查集就无能为力了，这时就要用种类并查集了。 2.因为有三种关系我们开三倍的pre数组，一倍的空间用来放同类，二倍的空间用来放食物，三倍的空间用来放天敌。 3。输入相应分类标志，判断当前的X,Y是否大于N。 4.根据分类条件分别先判断当前关系是否与前面冲突，如果冲突，错误加1，反之维护相应相应关系。 5.输出错误数量。

二.关系是否冲突

1.当输入为1 X Y 时，当前X,Y为同类，如果查找到X是Y``的食物或者X是Y的天敌时，即(find(X)==find(Y+N)或者 find(X)==find(Y+2N），错误+1。 2.1.当输入为2 X Y 时，当前X吃Y,如果查到X被Y吃，或者X,Y是同类时，即find(X)==find(Y),find(X)==find(Y+2N),错误+1.

三.关系的维护

1.输入1 X Y 时，1:X和Y为同类，X的食物与Y的食物，X的天敌与Y的天敌都是同类。（将X,Y合并，X+N,Y+N合并，X+2N，Y+2N合并） 2输入2.X Y时，因为（A 吃 B，B 吃 C，C 吃 A)，所以（X的食物与Y是同类，因为食物链成环Y的食物是X的天敌）因此将X与Y+2N，X+N与Y,X+2N与Y+N合并。

具体代码如下: