并查集的原理和应用

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 3 分钟

1. 结构实现

并查集要实现三个方法：

  1. int find(int x); 查找代表元素
  2. bool isSameSet(int x, int y); 查看是否为同一集合
  3. void _union(int x, int y); 合并集合

而并查集的结构，我们可以使用数组（顺序表）进行存储。数组下标i表示每个节点，数组的值father[i]对应着这个节点的代表节点。

对于father数组的初始化，我们有如下代码：

1
2
// 这里的n是节点总数
for (int i = 0; i < n; ++i) father[i] = i;

这样初始化，表示着每个节点一开始代表着自己。后期我们查找某个节点的代表节点的时候，只需依次跳转，直到father[i] == i就表示找到代表节点了

接下来，我们依次来看前面三种方法的实现

1.1 find

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

注意，这里在每次的递归中father[x] = find(x);保证最后的扁平化，保证时间复杂度保持在常数级别。

1.2 isSameSet

1
2
3
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}

查看代表元素是否相同，如果相同则表示在同一个集合中

1.3 _union

1
2
3
4
5
6
7
void _union(int x, int y) {
    int fx = find(x), fy = find(y);
    // 如果不是同一个集合 则进行合并
    if (fx != fy) {
        father[fx] = fy; // 只需修改代表节点即可合并
    }
}

2. 具体案例

990. 等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

这题我们可以将相等看作两个节点联通，或者说，这两个节点属于同一个集合。而不等式可以看作这两个节点不属于同一个节点。

也就是说，我们使用并查集，先将等式的组合进行合并，再根据不等式中的字母元素，判断该元素是否同属一个节点。一旦出现矛盾，则返回false

解题代码如下：

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
class Solution {
public:
    /*
        1. 对于所有的等式 可以看成合并操作
        2. 对应所有的不等式 看成这两个元素不在同一个集合中
    */
    vector<int> father;
    bool isEqual(string const& s) {
        return s[1] == '=';
    }
    int find(int x) {
        if (x != father[x]) father[x] = find(father[x]);
        return father[x];
    }
    void Union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
        }
    }
    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    bool equationsPossible(vector<string>& equations) {
        father.assign(26, 0);  
        for (char i = 'a'; i <= 'z'; ++i) father[i-'a'] = i-'a';
        for (auto s : equations) {
            if (isEqual(s)) Union(s[0]-'a', s.back()-'a');
        }
        for (auto s : equations) {
            if (!isEqual(s)) if (isSameSet(s[0]-'a', s.back()-'a')) return false;
        }
        return true;
    }
};