并查集提高——种类并查集（反集）

Table of Contents

• 前言：
  
• 引子题： P1892 [BalticOI 2003] 团伙
  
• 解法：
  
  
  • 以下为题解：
    
  
  
• 具体的运作流程：
  
• 例题22024 [NOI2001] 食物链
  
  
  • 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\) 是朋友，我们执行 unionset(u,v)，若 \(u,v\) 是敌人，我们 unionset(u+n,v) 、unionset(u,v+n);
朋友显然不需要解释，那么敌人为什么要这样合并呢，我们依据定义：所有i的敌人是i的敌对集的成员，那么谁和u的敌人共集呢，显然也是u的敌人，所以有了：unionset(u+n,v)，即将v加入u的敌人集；
那么谁和u共集呢，显然是v的敌人，所以有unionset(u,v+n)；
这样实际上利用了：敌人的敌人就是朋友这一性质，将无法维护（无法合并）的敌对关系换成了朋友关系；
接下来思考这样一个问题：若一个人同时是两个人的敌人，冲突吗；
你可能会觉得，这会冲突，因为根据集合的定义，不允许一个人同时归属两个集合，但是注意，我们使用的是并查集，这两个集合会合并，因此并不冲突；

以下为题解：

WriteUp 种类并查集解
我们定义，在 \(f_i\) 中，当 \(1 \le i \le n\) 时，为i的朋友集，当 \(n+1 \le i+n \le 2n\) 时，为i的敌对集；
当 \(u,v\) 是朋友，我们执行 unionset(u,v)，当 \(u,v\) 是敌人，我们 unionset(u+n,v) 、unionset(u,v+n);
下面给出AC代码：
[code]#includeusing namespace std;int n, m;char x;      // 操作符int fa[2006]; // 并查集数组，大小设为2*nint 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  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