并查集是一种可以动态维护若干个不重叠的集合，并支持合并与查询的数据结构。

并查集与路径压缩

并查集采用的方法是“代表元”的方法，在每个集合中选择一个元素来作为整个集合的“代表”。

并查集包含两个基本操作：

  1. Get，查询某一个元素属于哪一个集合，返回其“代表元”。
  2. Merge，合并两个集合。

路径压缩：路径压缩是并差集的基本优化方法，我们可以在每次执行 Get 操作的同时，把访问过的每个节点都直接指向树根。采用路径压缩优化的并查集，每次 Get 操作的均摊复杂度为 $O(logN)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fa[SIZE];
// 初始化每个集合都只有一个元素且自己作为元素的代表
for (int i = 1; i <= n; i++) {
  	f[i] = i;
}

int get(int x) {
  	if (fa[x] == x) return x;
  	return fa[x] = get(fa[x]);
}

void merge(int x, int y) {
  	fa[get(x)] = get(y);
}

带“边权”的并查集

在维护并查集时，我们可以同时维护一个数组 $d[]$，用 $d[x]$ 保存节点 $x$ 到父节点 $fa[x]$ 之间的边权。这就需要在路径压缩之后，同时更新这些节点的所对应的边权值。这样我们就可以统计每个节点到树根之间路径上的一些信息。

例如，我们现在使用 $d[x]$ 来统计每个节点到其根节点之间的距离，$size[x]$ 表示以 $x$ 为根的子树的大小。则代码实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get(int x) {
  	if (x == fa[x])
      	return x;
  	int root = get(fa[x]);
  	d[x] += d[fa[x]];  // 维护数组d[]
  	return root;
}

void merge(int x, int y) {
  	x = get(x), y = get(y);
  	fa[x] = y;
		d[x] = size[y];
  	size[y] += size[x];
}

带”扩展域“的并查集

在有些问题中，我们需要对并查集的集合进行扩展来解除问题。例如

食物链

问题

动物王国中有三类动物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句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1≤N≤50,000）和K句话（0≤K≤100,000），输出假话的总数。

分析

使用扩展域的并查集：每个物种扩展为三个域。同类域 x_self，捕捉域 x_eat，天敌域 x_enemy。

若输入为 2、 X、 Y， 则表示X 吃 Y。若 x 和 y 是同类（x_self 与 y_self 在同一集合），或者 y 吃x（y_eat 与 x_self 在同一集合）则是假话。否则说的是真的，应该将 x_eat 与 y_self，x_self 与 y_enemy，同时由于食物链只有x y z，所以 y 要吃的物种和 x 的天敌是同一类，因此还要将 y_eat 与 x_enemy 合并。

若输入为 1、 X、 Y，则表示 X和Y是同类。若 X 吃 Y（x_eat 与 y_self 在同一集合），或者 Y 吃 X（y_eat 与 x_self 在同一集合）则是假话。否则说的是真的，应该将 x_self 与 y_self，x_eat 与 y_eat，x_enemy 与 y_enemy 合并。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int fa[50000*3+1];
int n, k;
 
int getFa(int x) {
    if (x == fa[x]) return x;
    return fa[x] = getFa(fa[x]);
}
 
void mergeUnion(int x, int y) {
    int xfa = getFa(x);
    int yfa = getFa(y);
 
    fa[xfa] = yfa;
}
 
bool inSameRange(int x, int y) {
    int xfa = getFa(x);
    int yfa = getFa(y);
    return xfa == yfa;
}
 
int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= 3*n; ++i) {
        fa[i] = i;
    }
    int falseNumber = 0;
    for (int i = 0; i < k; ++i) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);
        if ((d == 2 && x == y) || (x > n || y > n)) {
            falseNumber++;
            continue;
        }
 
        int x_self = x, x_eat = x+n, x_enemy = x+2*n;
        int y_self = y, y_eat = y+n, y_enemy = y+2*n;
        if (d == 2) {  // x eat y
            if (inSameRange(x_self, y_self) || inSameRange(y_eat, x_self)) {
                falseNumber++;
                continue;
            }
            // mergeUnion(x_eat, y_enemy);
            mergeUnion(x_eat, y_self);
            mergeUnion(x_self, y_enemy);
            mergeUnion(y_eat, x_enemy);
        } else {  // x is as same as y
            if (inSameRange(x_self, y_eat) || inSameRange(x_eat, y_self)) {
                falseNumber++;
                continue;
            }
            mergeUnion(x_self, y_self);
            mergeUnion(x_eat, y_eat);
            mergeUnion(x_enemy, y_enemy);
        }
    }
    printf("%d\n", falseNumber);
 
    return 0;
}