并查集能快速处理以下操作：

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合中

时间复杂度近乎 O(1)

基本原理

每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x] 表示 x 的父节点。

如何判断树根？

if(p[x] == x)

如何求集合编号？

while(p[x]!=x) x=p[x];

如何合并两个集合？

p[x] = y

优化

每次找到根节点后，进行路径压缩。

模板题

原题链接

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

const int N = 100010;

int p[N];
int n,m;

// 返回 x 所在集合的编号（祖宗节点） + 路径压缩。
int find(int x) {
    // 只要 x 的父节点不是祖宗节点，就让 x 的父节点指向 x 的祖宗节点
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        p[i]=i;
    }
    while(m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(op[0] == 'M') {
            // 让 a 的祖宗节点的父亲等于 b 的祖宗节点
            p[find(a)] = find(b);
        } else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

连通块中点的数量

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

const int N = 1e5 + 10;

int n, m;

int p[N];
int cnt[N];

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

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) {
        p[i] = i;
        // 初始时每个集合中的元素都是 1
        cnt[i] = 1;
    }
    while(m--) {
        char op[4];
        scanf("%s", op);
        int a, b;
        if(op[0] == 'C') {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) continue;
            // 在把 a 集合并入 b 集合前，更新 b 集合中的元素数量
            cnt[find(b)]+=cnt[find(a)];
            // 将 a 集合与 b 集合连通
            p[find(a)] = find(b);
        } else if(op[1] == '1') {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        } else if(op[1] == '2') {
            scanf("%d", &a);
            printf("%d\n", cnt[find(a)]);
        }
    }
    return 0;
}

食物链

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

int n, k;
const int N = 50010;

// d[x] 表示节点 x 到节点 p[x] 的距离
int p[N], d[N];

int find(int x) {
    if(p[x]!=x) {
        // 记录 x 的祖宗节点编号
        int t = find(p[x]);
        // x 节点到父节点的距离加上父节点到祖宗节点的距离等于 x 节点到祖宗节点的距离
        // 因为再下一行会改变 p[x] 为 x 的祖宗节点，这里需要维护 d[x] 的含义：节点 x 到节点 p[x] 的距离，所以 d[x] 的值要变成节点 x 到节点 x 的祖宗节点的距离。
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main() {
    int res = 0;
    int t, x, y;
    cin >> n >> k;
    for(int i=0;i<n;i++) {
        p[i] = i;
    }
    while(k--) {

        cin >> t >> x >> y;
        if(x>n||y>n) res++;
        else {
            int px = find(x), py = find(y);
            if(t==1) {
                if(px == py && (d[x]-d[y])%3) res++;
                else if(px!=py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            } else {
                if(px == py && (d[x]-d[y]-1)%3) res++;
                else if(px!=py){
                    p[px] = py;
                    d[px] = d[y]+1-d[x];
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}