Sakana~
0%

【算法学习笔记】02 并查集

发表于 更新于 分类于

带权并查集

【算法学习笔记】02 并查集

没啥原理可讲的…存下板子和例题
形象的比喻：相当于找爸爸

基础

以下为并查集的基础操作：

初始化

1
2
3
4
void init () {
    for (int i = 1; i <= n; i ++)
        fa[i] = i;
}

查找（路径压缩版本）

路径压缩：把在路径上的每个节点都直接连接到根上

1
2
3
4
5
int find (int x) {
    if (x != fa[x])
        fa[x] = find (fa[x]);
    return fa[x];
}

注：路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集。

合并

1
2
3
4
void Union (int x, int y) {
    x = find (x), y = find (y);
    fa[x] = y;
}

启发式合并

小的连到大的上面
点数和深度中选一个作为估价函数

选点数为估价函数：按秩合并

1
2
3
4
5
6
7
8
9
10
std::vector<int> rk(N, 1);  // 初始化子树的大小为 1

void Union (int x, int y) {
    x = find (x), y = find (y);
    if (x == y) return;
    if (rk[x] > rk[y])  // 保证小的合到大的里
        swap(xx, yy);
    fa[x] = y;
    rk[y] += rk[x]; //注意不要反了
}

带权并查集

多分类问题：相对思想
应用之类的会比较多

原理

带权并查集不仅记录集合的关系，还记录着从当前节点到根节点的有向距离 (本质是带权图）
==记录与根节点之间的权值关系==

向量偏移法：

集合内的任意两个元素 x,y 必然存在某种联系（并查集的实质：并查集中的元素均是有联系的）
把两元素之间的关系量转化为 偏移量
即 x y 在集合里的有向距离为 v[y]-v[x]

遵循矢量运算法则：

==公式：y 到 x 的一条边距离为 w, 令**fa[xx]=yy, ** 则 v[xx]=-v[x]+v[y]-w==

查找

经路径压缩，父节点直接变根节点
当前节点的权值加上原本父节点的权值，就得到当前节点到根节点的权值
相对路径是不变的，故有 v’[i]=v[i]+v’[root]

==注意一定要先记录原来父节点的编号！==这点非常易错

1
2
3
4
5
6
7
8
int find (int x) {
    if (x != fa[x]) {
 	int t = fa[x]; //记录原父节点编号
	fa[x] = find(fa[x]); //父节点变为根节点，此时value[x]=父节点到根节点的权值
	v[x] += v[t]; //当前节点的权值加上原本父节点的权值      
    }
    return fa[x];
}

合并

x到yRoot两条路径的权值之和应该相同

图源：https://www.cnblogs.com/zhxmdefj/p/11117791.html

1
2
3
4
5
6
7
void Union (int x, int y) {
    int xx = find (x), yy = find (y);
    if (xx != yy) {
        fa[xx] = yy;
        v[xx] = v[y] - v[x] + s; //有时候可能会取模
    }
}

可以参照经典例题食物链的题解来辅助对于带权并查集的理解

扩展域并查集

枚举思想

并查集应用

https://oi-wiki.org/topic/dsu-app/

例题

以下为提高课例题：

1250. 格子游戏

https://www.acwing.com/problem/content/description/1252/

分析

并查集判环

  1. 坐标化为一维，映射坐标 (x,y)-> nx+y
  2. 出现环的时候，等价于两个点在连边之前已经在集合里

然后模拟操作，挨个判断即可

Code

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
#include <bits/stdc++.h>

using namespace std;
const int N = 205*205+205;
int n, m, fa[N];

int get_id (int x, int y) {
    return x * n + y;
}

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

int main () {
    cin >> n >> m;
    for (int i = 1; i <= N; i ++)    fa[i] = i;
    for (int i = 1; i <= m; i ++) {
        int x, y, a, b;
        char op;
        cin >> x >> y >> op;
        a = get_id(x, y);
        if (op == 'D')  b = get_id (x+1, y);
        else    b = get_id (x, y+1);

        a = find (a), b = find (b);
        if (a == b) {
            cout << i << endl;
            return 0;
        }
        fa[a] = b;
    }
    cout << "draw\n";
}
//dsu判环

1252. 搭配购买

https://www.acwing.com/problem/content/1254/

分析

把一个连通块看成一个物品，总体积总价值绑定到根节点
dsu + 01背包

Code

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
#include <bits/stdc++.h>

using namespace std;
const int N = 10005;
int fa[N], v[N], w[N], f[N];
int n, m, W;

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

int main () {
    cin >> n >> m >> W;
    for (int i = 1; i <= n; i ++)  fa[i] = i, cin >> v[i] >> w[i];
    while (m --) {
        int a, b;
        cin >> a >> b;
        a = find (a), b = find (b);
        if (a != b) {
            fa[a] = b;
            v[b] += v[a], w[b] += w[a];
        }
    }

    for (int i = 1; i <= n; i ++) {
        if (fa[i] == i)
            for (int j = W; j >= v[i]; j --)
                f[j] = max (f[j], f[j-v[i]] + w[i]);
    }

    cout << f[W] << endl;

}

237. 程序自动分析

https://www.acwing.com/problem/content/239/

分析

判断前后是否矛盾，是带权并查集的经典应用。
其实是矢量运算的加减，来连边
但是由于这里只有等和不等，所以可以直接判断是否在一个集合中

注：要记得离散化
坑1：2e5

坑2：map过不了
注意区别

Code

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
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, m, fa[N];
unordered_map<int, int> mp;

struct Node {
    int a, b, type;
}e[N];

int Hash (int x) {
    if (!mp.count (x))
        mp[x] = ++ n;
    return mp[x];
}

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

void solve () {
    mp.clear();
    n = 0;
    cin >> m;

    for (int i = 0; i < m; i ++) {
        int a, b, type;
        cin >> a >> b >> type;
        e[i] = {Hash(a), Hash(b), type};
    }

    for (int i = 1; i <= n; i ++)   fa[i] = i;

    //Union
    for (int i = 0; i < m; i ++) {
        if (e[i].type == 1) {
            int a = e[i].a, b = e[i].b;
            a = find (a), b = find (b);
            fa[a] = b;
        }
    }

    //check
    for (int i = 0; i < m; i ++) {
        if (e[i].type == 0) {
            int a = e[i].a, b = e[i].b;
            a = find (a), b = find (b);
            if (a == b) {
                cout << "NO\n";
                return ;
            }
        }
    }
    cout << "YES\n";
}

int main () {
    int t;  cin >> t;
    while (t --)    solve ();
}

239. 奇偶游戏

https://www.acwing.com/problem/content/241/

分析

大佬题解

Code

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
#include <bits/stdc++.h>

using namespace std;
const int N = 2e4 + 5;
int n, m;
int fa[N], v[N];
unordered_map <int, int> mp;

int Hash (int x) {
    if (!mp.count (x))
        mp[x] = ++ n;
    return mp[x];
}

int find (int x) {
    if (x != fa[x]) {
        int t = fa[x];
        fa[x] = find (fa[x]);
        v[x] += v[t];
    }
    return fa[x];
}

int mod2 (int x, int y) {
    return ((x + y) % 2 + 2) % 2;
}

int main () {
    cin >> n >> m;
    n = 0;
    for (int i = 0; i < N; i ++)    fa[i] = i;

    int ans = m;
    for (int i = 1; i <= m; i ++) {
        int a, b, t;
        string op;
        cin >> a >> b >> op;

        if (op == "even")   t = 0;
        else    t = 1;
        a = Hash (a - 1), b = Hash (b);
        int aa = find (a), bb = find (b);

        if (aa != bb) {
            fa[aa] = bb;
            v[aa] = v[b] - v[a] + t;
        }
        else {
            if (mod2 (v[a], v[b]) != t) {
                ans = i - 1;
                break;
            }
        }
    }
    cout << ans << endl;
}

238. 银河英雄传说

https://www.acwing.com/problem/content/240/

分析

依旧是带权并查集，维护的是到根节点的距离
距离之差就可求出之间隔了多少个点

Code

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
#include <bits/stdc++.h>

using namespace std;
const int N = 30005;
int fa[N], sz[N], v[N];

int find (int x) {
    if (x != fa[x]) {
        int t = fa[x];
        fa[x] = find (fa[x]);
        v[x] += v[t];
    }
    return fa[x];
}

int main () {
    for (int i = 0; i < N; i ++) {
        fa[i] = i;
        sz[i] = 1;
    }
    int m;
    cin >> m;
    while (m --) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        int pa = find (a), pb = find (b);
        if (op == 'M') {
            if (pa == pb)   continue;
            fa[pa] = pb;
            v[pa] = sz[pb]; //先
            sz[pb] += sz[pa];
        }
        else {
            if (pa != pb)   cout << "-1\n";
            else    cout << max (abs (v[a] - v[b]) - 1, 0) << endl;
        }
    }
}

题单

kuangbin：https://vjudge.net/contest/66964
板子题：https://www.luogu.com.cn/training/3065#problems
提高：https://www.luogu.com.cn/training/5085#problems

$Reference$：
https://www.cnblogs.com/zhxmdefj/p/11117791.html (必看)
https://zhuanlan.zhihu.com/p/34929966
https://oi-wiki.org/ds/dsu/
https://zhuanlan.zhihu.com/p/351139646
https://zhuanlan.zhihu.com/p/97813717