并查集及其补集应用

提起并查集，相信各位dalao并不陌生，甚至那就2行的板子已经被你们玩烂了……

并查集是一种树型的数据结构，它常用于处理一些不相交集合的合并及查询问题，而最常见也是最简单的问题就是找亲戚：

有1，2，3，4，5这么几个人，告诉你两个人是不是亲戚，之后询问两个人的关系。

比如知道1，3是亲戚，3，4是亲戚，起初要把每个点所在集合的代表初始化为其自身，随后合并1，3所在集合和3，4所在集合，那么随后询问时我们会知道1，4在同一集合，是亲戚。

这就是简单的并查集的应用，它形成的是一个森林，就是使用树来表示集合，树的每个节点就表示集合中的一个元素，树根的元素就是该集合的代表。而对于给定的元素，可以很快的找到这个元素所在的集合是什么，以及合并两个元素所在的集合，从而实现了对于任意两个元素是否在同一集合的判断。

并查集还有常见的两种优化，一是路径压缩，二是启发式合并。第一种是几乎必用的，第二种主要应对充满恶意的非随机数据，绝大多数情况下可以不用。

1 class Union_Find_Set {
2     private:
3         const int maxn = 500000 + 10;
4         int p[maxn];  //每个元素所在集合的代表
5     public:
6         inline void Refl(int x) { for(int i=1; i<=x; ++i) p[i] = i; }  //初始化
7         int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); }  //查询所在集合
8         inline void Unio(int x, int y) { p[ Find(x) ] = Find(y); }  //合并两个集合
9 }

这个东西真的有用吗？能吃吗？答案是肯定的。

这是个很方便的数据结构，它每个操作的时间都是接近常数时间的，可以被用于求最小生成树，联通子图，以及最近公共祖先等等。

而它还可以人为地搞一个几倍大小的补集用于维护元素的其它关系。

在做一个并查集时，我们将空间开到几倍大小，用第一段（1~n）与第二段（n+1~2*n），第三段……之间的联系维护元素与元素不同的关系，很明显，p[i] 与 p[n+i]，p[2*n+i]……将拥有不同的意义，而这也就是补集的意义与方便之处。在实际应用中的做法已经显而易见，只需要倍开空间，记住自己对每一段给他的意义，然后实现代码就好。

一道例题：Luogu P2024

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B吃 C，C 吃 A。

现有 N 个动物，以 1 － 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 句话。

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

1 ≤ N ≤ 5 ∗ 10^4

1 ≤ K ≤ 10^5

这是一道毫无修饰的，利用并查集补集完成的题目。而且由于只有3种动物，我们很方便地可以开3倍空间，用第一段表示种类，第二段表示其食物，第三段表示其天敌，关系就一目了然了。

见代码：

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 50000 + 10;
 8 int n, k, p[3 * maxn], ans;
 9 
10 inline void Refl(int x) { for(int i=1; i<=3*x; ++i) p[i] = i; }  
11 int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]); }
12 inline void Unio(int x, int y) { p[ Find(x) ] = Find(y); }
13 
14 inline void read(int &x) {
15     register char ch = 0;  x = 0;
16     while( !isdigit(ch) ) ch = getchar();
17     while( isdigit(ch) ) x = (x*10) + (ch^48), ch = getchar();
18 }
19 
20 int main(int argc, char const *argv[])
21 {
22     scanf("%d%d", &n, &k);
23     int ques, a, b;  Refl(n);
24     while( k-- ) {
25         read(ques), read(a), read(b);
26         if( a>n || b>n ) { ++ans; continue; }
27         if( ques==1 )
28             if( Find(n+a)==Find(b) || Find(n+b)==Find(a) )  ++ans;
29                 /* 如果存在a吃b或者b吃a的关系，那他们不是一种动物 */
30             else Unio(a, b), Unio(n+a, n+b), Unio(2*n+a, 2*n+b);
31                 /* 否则把他们的三种属性全关联起来 */
32         else
33             if( Find(a)==Find(b) || Find(a)==Find(n+b) )  ++ans;
34                 /* 如果已知a和b是同种动物或者是b吃a的关系，这句话是假话 */ 
35             else Unio(n+a, b), Unio(a, 2*n+b), Unio(2*n+a, n+b);
36                 /* 否则是真话，按照捕食关系关联起来 */
37                 /* 因为只有三种动物，所以如果a吃b，则a是b的天敌且被b的食物吃 */ 
38     }
39     printf("%d
", ans);
40     return 0;
41 }

暂时写到这里好了，以后想起什么详细的解释再补充w。

　　　　　　　　　　　　　　　　　　　　　　　　　—— 信じてた今でさえ believe in 願う。