跳转至

并查集

普通并查集

  • 并查集可以维护无向连通性，并支持动态加边；
  • 并查集可以维护染色问题：每次操作给定两种颜色 \(a,b\)，将所有颜色为 \(a\) 的点染为 \(b\)；
int fa[N];
void init() {
    for(int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(y)] = find(x);
}

P4119 [Ynoi2018] 未来日记

见分块

YbtOj 沧海桑田

题目大意

有一张 \(50\times 10^5\) 的网格图，初始时所有位置都是海洋。你需要维护两种操作：

  • 给定一个矩形，将矩形内所有位置更改为陆地；
  • 给定两个点，询问它们之间的陆地是否连通；

注意到没有将陆地改变为海洋的操作，因此海洋变为陆地的总次数是均摊 \(O(nm)\) 的，因此可以使用并查集维护陆地连通块。

考虑如何找到矩形内剩余海洋。我们维护 \(f_{x,y}\) 表示第 \(x\) 行 \(y\) 列位置，向右第一个海洋的下标。如果 \((x,y)\) 就是海洋，则 \(f_{x,y}=y\)；其余情况 \(f_{x,y}=f_{x,y+1}\)。

将 \((x,y)\) 位置从海洋修改为陆地等价于将 \(f_x\) 中所有 \(y\) 修改为 \(f_{x,y+1}\)。注意到这正是一种染色问题，仍然可以使用并查集维护。

代码 
 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
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;
const int N = 1E5 + 10;
const int M = 55;

int change(int x, int y) {
    return x * N + y;
}

int t;
int col[N * M];

int nxt[N * M];
int findNext(int x) {
    if(nxt[x] == x) return x;
    return nxt[x] = findNext(nxt[x]);
}

int fa[N * M];
int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

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

bool in_bound(int x) {
    return 1 <= x && x < N * M;
}

void update(int x) {
    col[x] = 1;
    if(in_bound(x + 1) && col[x + 1]) merge(x, x + 1);
    if(in_bound(x - 1) && col[x - 1]) merge(x, x - 1);
    if(in_bound(x + N) && col[x + N]) merge(x, x + N);
    if(in_bound(x - N) && col[x - N]) merge(x, x - N);
}

int main() {

    for(int i = 1; i < N * M; i++) {
        nxt[i] = i;
        fa[i] = i;
    }

    cin >> t;
    while(t--) {
        int op, x1, y1, x2, y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        if(op == 0) {
            if(x1 > x2) swap(x1, x2);
            if(y1 > y2) swap(y1, y2);
            for(int i = x1; i <= x2; i++) {
                int j = change(i, y1);
                while(j <= change(i, y2)) {
                    update(j);
                    if(nxt[j] == j) nxt[j] = j + 1;
                    j = findNext(j);
                }
            }
        } else {
            if(col[change(x1, y1)] && col[change(x2, y2)] && find(change(x1, y1)) == find(change(x2, y2))) {
                cout << 1 << endl;
            } else cout << 0 << endl;
        }
    }

    return 0;
}

并查集优化

路径压缩

简洁，高效，常用，均摊复杂度

代码见上文

启发式合并

简洁，稍慢，非均摊

int fa[N], sz[N];
void init() {
    for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}
int find(int x) {
    if(fa[x] == x) return x;
    return find(fa[x]);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(sz[y] > sz[x]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
}

带权并查集

带权并查集通常用来维护带权连通性问题。

P1196 [NOI2002] 银河英雄传说

扩展域并查集

扩展域并查集通常用来维护动态 \(k\)-染色问题。

P2024 [NOI2001] 食物链

P5787 二分图 /【模板】线段树分治

见线段树分治