并查集（disjoint sets）

并查集（disjoint sets）学习笔记(python、C语言)

这个月刷leetcode已经遇到了三次并查集问题，前两次都看太难放过，今天又遇到就先尝试解决，看到师弟桌子上《挑战程序设计竞赛》这本书上有这个知识点，这里写下笔记记录。

---

---

前言

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

---

一、并查集是什么？

并查集是一种用来管理元素分组情况的数据结构。
可以高效进行如下操作

• 查询元素a和元素b 是否属于同一组。
• 合并元素a和元素b 所在的组

分组和对应的例子

二、并查集的结构

并查集是树形结构。不过，不是二叉树。

每个元素对应一个节点，每个组对应一颗树。

在并查集中，哪个节点是哪个节点的父亲以及树的形状等信息不用关注，整体是树形结构才最重要

1. 初始化

2. 合并

和下面图一样，从一个组的根向另一个组的跟连边，将两棵树变成 一颗树，也就是两个组变成一个组

3. 查询

为了查询两个节点是否同一组，只要沿着树向上走，查询根节点是否相同，根节点相同时同一组，否则不同组。如上图中 （2）（5）的根是 （1），而（7）的根是（6） 所以（2）和（5）是同一组，但是（2）和（7）不是同一组。

并查集实现的注意点

在树形数据结构中，如果发生退化情况（二叉树退化为一维链表），那么时间复杂度会变的很高。在并查集中，只需按照如下方法就可以避免退化。

• 对于每棵树，记录树的高度（rank）
• 合并时，如果两棵树的rank不同，那么rank小的向rank大的连边。

此外，通过路径压缩，可以使并查集更高效率。对于每个节点，一旦向上走到了一次根节点，就把这个点到父亲的边改成为直接连向根。
如需要查询（7），就可以直接将（7）连接到根上。

在此之上，不仅查询的节点，所有在查询过程中经过的所有节点，都可以直接连接到根上。再次查询时，就可以很快查询到根是谁了。
如下，将（2）（3）（4）（5）都连接到（1）中。

在使用这种化简方法时，为了简单起见，即使树的高度发生变换，也不再修改rank。

查并集的复杂度

加入两个优化后，查并集的效率非常高。对n个元素的查并集进行一次操作的复杂度为$O(a(n))$。在这里$a(n)$时阿克曼(Ackermann)函数的反函数。这要比$O(log(n))$还要快。

不过，这是“均摊复杂度”。并不是每次都满足，多次后，平均每次复杂度。

并查集的实现

数组par表示父亲编号，$par[x]=x$时， $x$是树的根

int par[MAX_N];    // 父亲
int rank[MAX_N];    // 树的高度

// 初始化n个元素
void init(int n) {
    for (int i = 0); i < n; i++){
        par[i] = i;
        rank[i] = 0;
        }
    }

// 查询树的根
int find(int x){
    if (par[x] == x):
        return x;
    }
    else{
    return par[x] = find(par[x]);
    }
}

// 查询x和y所属集合
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;
    
    if (rank[x] < rank[y]){
        par[x] = y;
        } else {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}

// 判断x和y是否属于同一集合
bool same(int x, int y){
    return find(x) == find(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
35
36
37
38
39

python 实现

class UnionFind:
    def __init__(self, nums):
        self.par = list(range(len(nums)))
        self.rank = [0] * len(nums)
    
    # 查询树的根   
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
        
    # 查询x个y所属集合   
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 判断x和y是否为同一集合
    def same(self, x, y):
        return self.find(x) == self.find(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

示例 LeetCode 1202. 交换字符串中的元素

题目链接：: 交换字符串中的元素.
题目：
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以任意多次交换在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"

解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

示例 2：

输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"

解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

答案代码：

class UnionFind:
    def __init__(self, nums):
        self.par = list(range(len(nums)))
        self.rank = [0] * len(nums)
    
    # 查询树的根   
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
        
    # 查询x个y所属集合   
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 判断x和y是否为同一集合
    def same(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        uf = UnionFind(s)
        i = 0
        # 寻找根节点
        for k, v in pairs:
            uf.unite(k, v)
        
        # 获取根节点对应的连通块集合
        dic = collections.defaultdict(list)
        for i in range(len(s)):
            root = uf.find(i)
            dic[root].append(i)
        # 对每个连通块中元素排序
        res = list(s)
        for k, v in dic.items():
            arr = [s[i] for i in v]
            arr.sort()
            for i in range(len(v)):
                res[v[i]] = arr[i]
                
        return "".join(res)
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

总结

吐血整理啊，还是自己太菜了，看了一天。加油！