Aquabet

Talk is cheap. Show me the code.

0%

并查集

发表于 分类于

前言C

  最近刷每日一题，连着两天出了并查集，分别是 547. 省份数量 和 1202. 交换字符串中的元素 下面以 547. 省份数量 为例，简单阐述下并查集。

原理

  并查集是一种简洁实用的数据结构，通常用于判断两元素是否属于同一集合时使用。并查集只有两种操作，合并集合和查询集合。
  并查集中引入了代表元素的概念，即用一个元素来代替整个集合。可以把并查集类比为一颗树，树是从上往下的有向图，并查集是从下往上的有向图。这样，一个树上的所有节点最终都能找到树的根节点，也就是说，集合的所有元素都能找到并查集的代表元素。

初始化

  将每个元素的父节点初始化为自己。

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

并操作

  并操作将两个集合合并到同一集合。只需要一个元素的代表元素(A)认另一个元素的代表元素(B)当爹就行。这样，A集合和B集合都变为了B集合，两个集合合并为了同一个集合。

1
2
3
4
5
6
7
for(int i = 0; i < n; i++) {
    for(int j = 0; j < i; j++) {
        if(isConnected[i][j] == 1) {//如果联通，合并。
            fa[findfa(fa,j)] = findfa(fa,i);
        }
    }
}

查操作

  查操作通常使用递归，不停地找父节点。直到找到一个节点的父节点是这个节点本身，那么这个节点就是待查元素的代表元素。

1
2
3
4
5
6
int findfa(int *fa, int p) {
    if(fa[p] != p) {
        return findfa(fa,fa[p]);
    }
    return p;
}

  理解了并查集的基本操作，剩下就顺着题意写就完事。

完整代码

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
class Solution {
public:
    int findfa(int *fa, int p) {
        if(fa[p] != p) {
            return findfa(fa,fa[p]);
        }
        else {
            return p;
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        if(n == 0) return 0;
        int fa[n];
        int ans = 0;
        bool read[n];
        memset(read, false, sizeof(read));
        for(int i = 0; i < n; i++) {
            fa[i] = i;
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(isConnected[i][j] == 1) {
                    fa[findfa(fa,j)] = findfa(fa,i);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            int thisfa = findfa(fa,i);
            if(read[thisfa] == false) {
                ans++;
                read[thisfa] = true;
            }
        }
        return ans;
    }
};

路径压缩

  对于层数较高且查询的次数要求较高时，上面所示的并查集并不能高效地完成所需要求。因此我们引入了并查集的路径压缩。对于路径压缩，我们只需要修改并操作的代码，把构造一个棵树改为构造一棵层数为1的树仙人掌。在一般情况下，路径压缩的并查集把并操作的效率略微降低，查操作的效率提高，在刷题时可以取舍使用。

更多

  并查集是应用极广的数据结构，最小生成树的Kruskal算法也常通过并查集来写。
  Kruskal算法的主要思想：以边为主导地位，始终选择当前可用的最小边权的边（sort或priority_queue）并加入集合，下面展示Kruskal的核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int father(int x) {//找代表元素，并查集的一部分
    if(fat[x] != x) {
        return father(fat[x]);
    }
    return x;
}

void unionn(int x, int y) {//加入团体，并查集的一部分
    fat[father(y)] = father(x);
}

if(father(edge[i].from) != father(edge[i].to)) {//假如不在一个团体
    unionn(edge[i].from, edge[i].to);//加入 
    tot += edge[i].dis;//记录边权 
    k++;//已连接边数+1 
}