前言：
引子题： P1892 [BalticOI 2003] 团伙
解法：
1. 以下为题解：
具体的运作流程：
例题2:P2024 [NOI2001] 食物链
1. WriteUp：
补充：
结语：

前言：

本蒟蒻在今天刷题时遇到了种类并查集的问题，遂决定，花1小时学学，并写篇文章记录一下；
那么如果你认真读完本文，你将自己发明

种类并查集（反集）

；
前置知识：

普通并查集

；

普通并查集

引子题： P1892 [BalticOI 2003] 团伙

## 题目描述
现在有 \(n\) 个人，他们之间有两种关系：朋友和敌人。我们知道：

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

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

## 输入格式
第一行输入一个整数 \(n\) 代表人数。
第二行输入一个整数 \(m\) 表示接下来要列出 \(m\) 个关系。
接下来 \(m\) 行，每行一个字符 \(opt\) 和两个整数 \(p,q\)，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 \(opt\) 有两种可能：

如果 \(opt\) 为 `F`，则表明 \(p\) 和 \(q\) 是朋友。
如果 \(opt\) 为 `E`，则表明 \(p\) 和 \(q\) 是敌人。

## 输出格式
一行一个整数代表最多的团体数。

## 说明/提示
对于 \(100\%\) 的数据，\(2 \le n \le 1000\)，\(1 \le m \le 5000\)，\(1 \le p,q \le n\)。

解法：

上面的题在洛谷，可以自己尝试；

如果你没学过种类并查集（反集），你应该会想到使用并查集维护朋友关系，用数组维护敌人关系，随后遍历每个人的每个敌人的每个敌人，将这个人和他敌人的敌人合并；
但是，我们注意到，这样做的代价是：空间复杂度 \(O(n^2)\) ，时间复杂度 \(O(n^3)\) ；
若是题目的数据再大一个数量级，这么做会爆；
不过，这样也可以AC了这道题，毕竟还是比较水的；

如果你想到了维护敌人并查集，那你已经有了相当好的直觉，事实上，种类并查集也类似在维护一个新并查集；
但是，对于敌人并查集，这里的设定很关键：如果你设成一个集合内部是朋友，那么会非常复杂，问题是，你如何由敌对推出朋友呢，仍然需要存储每个人的敌人，这样做依然不好；
如果你设定一个集合内部是敌人，那么一个人和另一个人的关系仍然不好维护，因为如果是朋友关系，AB是朋友，BC是朋友，AC一定是朋友，但是对于敌对关系，AB是敌人，BC是敌人，AC就是朋友了；
这破坏了集合

传递性

（即若AB共集，BC共集，那么AC共集）；

我们先来反思一下为什么普通并查集不行：
最重要的是，敌人关系不满足集合的传递性这个数学要求，从而并查集不成立；
事实上，普通并查集维护的是两个人是不是共集的信息，而对于两个人各自的相对身份（注意：相对身份，A对于B是朋友，对于C可能就是敌人了）我们一无所知；
那么怎样维护这种多重身份呢；（换言之，怎样恢复传递性）

从传递性入手：朋友关系才具有传递性，所以我们要想办法将敌对关系换成朋友关系；
“敌人关系本身不传递，但敌人的敌人是朋友——这句话其实把‘敌对’转换成了‘朋友’，于是我们又可以用并查集了。”

若是我们开一个长度为 \(2n\) 的并查集
1.当 \(1 \le i \le n\) 时，i为其朋友集，所有与i是朋友关系的人会接到这个集合中（即普通的并查集）
2.当 \(n+1 \le i \le 2n\) 时，i(实际上是i+n)为敌对集，所有i的敌人都会接入这个集合中

若 \(u,v\) 是朋友，我们执行 union_set(u,v)，若 \(u,v\) 是敌人，我们 union_set(u+n,v) 、union_set(u,v+n);
朋友显然不需要解释，那么敌人为什么要这样合并呢，我们依据定义：所有i的敌人是i的敌对集的成员，那么谁和u的敌人共集呢，显然也是u的敌人，所以有了：union_set(u+n,v)，即将v加入u的敌人集；
那么谁和u共集呢，显然是v的敌人，所以有union_set(u,v+n)；
这样实际上利用了：敌人的敌人就是朋友这一性质，将无法维护（无法合并）的敌对关系换成了朋友关系；

接下来思考这样一个问题：若一个人同时是两个人的敌人，冲突吗；
你可能会觉得，这会冲突，因为根据集合的定义，不允许一个人同时归属两个集合，但是注意，我们使用的是并查集，这两个集合会合并，因此并不冲突；

以下为题解：

WriteUp 种类并查集解
我们定义，在 \(f_i\) 中，当 \(1 \le i \le n\) 时，为i的朋友集，当 \(n+1 \le i+n \le 2n\) 时，为i的敌对集；
当 \(u,v\) 是朋友，我们执行 union_set(u,v)，当 \(u,v\) 是敌人，我们 union_set(u+n,v) 、union_set(u,v+n);
下面给出AC代码：

#include<iostream> using namespace std; int n, m; char x; // 操作符 int fa[2006]; // 并查集数组，大小设为2*n int t1, t2; int ans; bool vis[2006]; // 用于标记已统计的根节点 int findx(int x) { return x == fa[x] ? x : fa[x] = findx(fa[x]); } void union_set(int x, int y) { int rx = findx(x), ry = findx(y); if (rx != ry) { fa[rx] = ry; } } int main() { cin >> n >> m; for (int i = 1; i <= 2 * n; i++) { fa[i] = i; } for (int i = 1; i <= m; i++) { cin >> x; if (x == 'F') { cin >> t1 >> t2; union_set(t1, t2); } else { cin >> t1 >> t2; union_set(t1 + n, t2); union_set(t1, t2 + n); } } // 路径压缩所有主要节点 for (int i = 1; i <= n; i++) { findx(i); } // 统计不同根节点 for (int i = 1; i <= n; i++) { int root = findx(i); if (!vis[root]) { vis[root] = true; //统计所有不一样的根，因为可能有的以敌人集为根 ans++; } } cout << ans << endl; return 0; }

具体的运作流程：

我们先定义这样一些关系，方便演示：
1 2 是朋友，1 3 是朋友
1 4 是敌人，4 5 是敌人；

根据我们的定义，最终，1235是一个集合
接下来看图：
我们先加入朋友边，不难发现，1 2 3形成了一个联通的区域，我们称为一个联通块，显然，同一个联通块是一个集合；
随后，加入（1，4反集），（1反集，4）这两个敌人边，即（1，9）（6，4），这里n=5，一共五个人；
现在出现了两个联通块，分别是：（1，2，3，4反），（4，1反）；
我们继续加入4，5的敌人关系，就是：（4，5反）（4反，5），即（4，10）（9，5）；

不难发现，现在，并查集已经正确处理了所有的关系；
更准确的说，4的反集是一个中间量，建立起了1和5的朋友关系（由于4的敌人和1是一个集，所以1，5共集），这就是反集的作用，它通过转换，维护了不具备传递性的敌人关系；

这里有个坑，不难发现，我在代码中使用了vis数组，这是由于敌人集可能是根，也需要一并统计；

例题2: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\) 句话，输出假话的总数。

## 输入格式

第一行两个整数，\(N,K\)，表示有 \(N\) 个动物，\(K\) 句话。
第二行开始每行一句话（按照题目要求，见样例）

## 输出格式
一行，一个整数，表示假话的总数。

WriteUp：

这道题我们可以通过扩展并查集（种类并查集）来做，也可以使用加权并查集；
当然，由于还没讲到加权并查集，这里使用扩展并查集；
补充一个点：有几种关系就要开几倍的并查集；

接下来分析一下这道题：
一共三种动物，A吃B，B吃C，C吃A，所以我们开 \(3 \times n\) 的种类并查集；
那么一共两种情况（我们先假设都为真）：1. \(X\) 和 \(Y\) 是同类，2. \(X\) 吃 \(Y\) ；
细分下去，当 \(X\) 和 \(Y\) 是同类时，我们其实不知道 \(X\) 和 \(Y\) 具体属于AA、BB还是CC，因此，我们需要合并3个集合中的XY，这代表XY是同类
同样，当 \(X\) 吃 \(Y\) 时，我们也不知道是AB、BC还是AC，同样需要合并x的A集和y的B集、x的B集和y的C集、x的C集和y的A集；

上面的分类不好理解，更准确的讲，我们称A集为本体集，B集为猎物集，C集为天敌集

对于同类，同类的天敌就是天敌，同类的猎物就是猎物
对于y是x的猎物，将y加入x的猎物集，将x加入y的天敌集，将x的天敌加入y的猎物集
（这里只有“将x的天敌加入y的猎物集”是不好理解的，我们进行一下推理：设z是x的天敌，由于y是x的猎物，x是z的猎物，那么z是y的猎物（因为C吃A））

那么，怎样判断一句话是否为假呢？
题目给了我们提示：

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

后两个比较好判断，关键是1，什么叫冲突；

根据真假逆命题的关系，我们反转条件，归结为下面的几类：
1.xy是同类，但是当前的话表示：x吃y或者y吃x；
2.x吃y，但是当前的话表示：y吃x、xy是同类

下面给出AC代码：

#include<cstdio> using namespace std; int n,k; int op,p,q; int ans; int fa[150004]; int findx(int x) { return x==fa[x]?x:fa[x] = findx(fa[x]); } void union_set(int u,int v) { int rx = findx(u),ry = findx(v); if (rx!=ry) { fa[ry] = rx; } } void init(int x) { for (int i=1;i<=x;i++) { fa[i] = i; } } bool is_not_lie(int o,int x,int y) { if (x>n || y>n) return false; //xy比n大 if (o==1) { if (findx(x)==findx(y+n)||findx(y)==findx(x+n)) { //x是y的猎物，或者y是x的猎物 return false; } }else { if (x==y) return false;//x吃x if (findx(x)==findx(y+n)) return false; //x是y的猎物 if (findx(x)==findx(y)) return false; //是同类 } return true; } int main() { scanf("%d %d",&n,&k); init(3*n); for(int i=1;i<=k;i++) { scanf("%d %d %d",&op,&p,&q); if (!is_not_lie(op,p,q)) { ans++; continue; }else { if (op==1) { union_set(p,q);// 同类 union_set(p+n,q+n);// 同类的猎物是猎物 union_set(p+2*n,q+2*n); // 同类的敌人是敌人 }else { union_set(p+n,q); //y是x的猎物 union_set(p,q+2*n);//x是y的天敌 union_set(p+2*n,q+n);//由 y->x->z->y 得x的天敌是y的猎物 } } } printf("%d",ans); return 0; }

补充：

1.对于第一题，普通做法是 \(O(n^3)\) 的，种类并查集做法是 \(O(n \alpha(a))\) 的，近似线性；
2.对于并查集的题目，可以采用先不编写函数实现，直接写main，之后依次实现需要的函数和变量的方法；
3.种类并查集是加权并查集的特例，这里面的两道题都可以使用加权并查集做，但是逻辑比较复杂，空间会更小（仍为普通并查集的大小，即 \(O(n)\) ）