简介

该数据结构的作用有如下两点：

  1. 合并两个集合。
  2. 查询两个元素是否在同一个集合中。

基本实现原理是把每个集合用一颗树表示，树根的编号是这个集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点，对于根节点，p[x] = x。

对于优化，可以在查找树根时将路径上的每一个节点的父节点都指向树根。

例题

一共有 nn 个数，编号是 11 ~ nn，最开始每个数各自在一个集合中。现在要进行 mm 个操作，操作共有两种：

  1. M a b，将编号为 aa 和 bb 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
  2. Q a b，询问编号为 aa 和 bb 的两个数是否在同一个集合中；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int p[N], n, m;

int root(int x) {
    if (p[x] != x) p[x] = root(p[x]);
    return p[x];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) p[i] = i;
    char op[2]; int a, b;
    while (m--) {
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'M') p[root(a)] = root(b);
        else puts(root(a) == root(b) ? "Yes" : "No");
    }
    return 0;
}

可以将 root 改成不递归的模式：

1
2
3
4
5
6
7
8
9
10
11
12
int root(int x) {
    int res = x;
    while (p[res] != res) res = p[res];

    int i = x;
    while (p[i] != i) {
        int par = p[i];
        p[i] = res;
        i = par;
    }
    return res;
}

但这显然不如递归的简练。实在想不起来递归的模板怎么写了再考虑这样用循环模拟一遍。

[NOI2002] 银河英雄传说（带权并查集）

有一个划分为 N 列的星际战场，各列依次编号为 1,2,…,N。

有 N 艘战舰，也依次编号为 1,2,…,N，其中第 i 号战舰处于第 i 列。

有 T 条指令，每条指令格式为以下两种之一：

  1. M i j，表示让第 i 号战舰所在列的全部战舰保持原有顺序，接在第 j 号战舰所在列的尾部。
  2. C i j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。

现在需要你编写一个程序，处理一系列的指令。

输入格式

第一行包含整数 T，表示共有 T 条指令。

接下来 T 行，每行一个指令，指令有两种形式：M i j 或 C i j。

其中 M 和 C 为大写字母表示指令类型，i 和 j 为整数，表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：

如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 i 号战舰与第 j 号战舰之间布置的战舰数目，如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 −1。

题目链接：AcWing 238，P1196。洛谷后面有图解样例。

用前缀和的思想，设 did_i 是 ii 到根节点的距离，那么两点间存在的点数应该是：

di,j={0,i=j∣di−dj∣−1,i≠jd_{i,j}=\left \{\begin{aligned} &0,i=j\\ &|d_i-d_j|-1,i\ne j \end{aligned}\right .

当合并两个集合 A,BA, B 时，设将 BB 合并到 AA， 那么集合 BB 中根节点的距离就要更新成 dB=∣A∣d_B=|A|，然后它的子节点求距离的时候就可以找到正确的跳板求解了。

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 30010;
int p[N], d[N], s[N];

int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

void solve() {
    char op[2];
    int i, j;
    scanf("%s%d%d", op, &i, &j);
    int pi = find(i), pj = find(j);
    if (*op == 'M') {
        if (pi != pj) {
            p[pi] = pj;
            d[pi] = s[pj];
            s[pj] += s[pi];
        }
    } else {
        if (pi != pj) puts("-1");
        else printf("%d\n", max(abs(d[i]-d[j]) - 1, 0));
    }
}

int main() {
    for (int i = 1; i < N; i++)
        p[i] = i, s[i] = 1;
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

[NOI2001] 食物链

动物王国中有三类动物 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 和 K 句话，输出假话的总数。

题目链接：AcWing 240，P2024。

结点 $u \to v $ 表示 uu 被 vv 吃，设某个点到根结点的距离为 dd，判断 d mod 3d\text{ mod }3 的取值：

  • 余 0：当前点和根结底为同类。

  • 余 1：当前点吃根结点。

  • 余 2：当前点被根节点吃。

于是如果给的两个点 u,vu, v 已经在集合中，就可以判断出它们的关系了。

当合并两个集合使 px→pypx \to py 的时候，如果 x,yx, y 是同类，那么要保证：

dx+dpx≡dy(mod 3)dpx≡dy−dx(mod 3)\begin{aligned} d_x+d_{px} &\equiv d_y(\text{mod } 3)\\ d_{px} &\equiv d_y-d_x(\text{mod } 3)\\ \end{aligned}

如果 xx 吃 yy 那么要使得：

dx+dpx≡dy+1(mod 3)dpx≡dy−dx+1\begin{aligned} d_x+d_{px}&\equiv d_y + 1(\text{mod }3)\\ d_{px}&\equiv d_y-d_x+1 \end{aligned} 

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50010;
int n, k, p[N], d[N];
int find(int x) {
    if (x != p[x]) {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) p[i] = i;
    
    int fake = 0;
    while (k--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (x > n || y > n) {
            fake++;
            continue;
        }
        
        int px = find(x), py = find(y);
        if (t == 1) {
            if (px == py) {
                if ((d[x] - d[y]) % 3 != 0) fake++;
            }
            else p[px] = py, d[px] = d[y] - d[x];
        } else {
            if (px == py) {
                if ((d[x] - d[y] - 1) % 3 != 0) fake++;
            } else p[px] = py, d[px] = d[y]-d[x]+1;
        }
    }
    cout << fake << endl;
    return 0;
}