算法图论

含集合级信息的并查集

字数统计: 3.1k字   |   阅读时长: 14分
, , ,

摘要: 带集合级信息的并查集的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 并查集 中我们学习了并查集的原理和代码模板，本文介绍带集合级信息的并查集。

我们知道并查集的结构是一个森林，其中的每一棵树表示一个集合或者一个连通分量，树根元素为该集合的代表元，树中的各个节点分别代表各个元素。

有时我们需要在合并的过程中维护连通分量的某种属性，比如元素个数、最值等等，称为集合级的权。维护这种集合级的权，只需要在基础的并查集上增加很少代码即可实现，下面直接给出一些题目。

题目 集合级的权表示的信息
128. 最长连续序列 连通分量的大小
面试题 17.07. 婴儿名字 连通分量的属性
952. 按公因数计算最大组件大小 连通分量的大小
1061. 按字典序排列最小的等效字符串 连通分量的最值
1632. 矩阵转换后的秩 连通分量的属性
928. 尽量减少恶意软件的传播 II 两种连通分量的权，大小和属性

带集合级信息的并查集，在合并过程中会对集合级信息带来变化，例如集合元素个数，连通分量中的最值，这些信息可以放在代表元(树根)维护。并查集的查找过程对集合级信息没有影响，因为路径压缩影响的只是非根节点。

下面通过一些题目来看一下含集合级信息的并查集如何使用。

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示：

1
2
0 <= nums.length <= 1e5
-1e9 <= nums[i] <= 1e9

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

算法1：哈希表

将 nums 中的元素倒入哈希表中。然后枚举哈希表中的所有元素，对于元素 i，首先判断 i - 1 是否在哈希表中：

  • 如果不在：说明 $i$ 是一个连续序列的最小元素，然后依次枚举 $i + 1, i + 2，\cdots$ 直至枚举到的值 $i + k$ 不在哈希表中，则 $i, i + 1, \cdots, i + k - 1$ 就是一个连续序列，长度为 $k$。
  • 如果在：说明 $i$ 不是一个连续序列的最小元素，直接跳过，

代码 (C++)

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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) 
            return 0;
        unordered_set<int> setting;
        for(int num: nums)
            setting.insert(num);

        int result = 0;
        for(int num: setting)
        {
            if(num != INT_MIN && setting.count(num - 1) > 0) // num 不是最左元素
                continue;
            // 找到了一个序列的最左元素
            int cnt = 1;
            ++num;
            while(setting.count(num) > 0)
            {
                ++cnt;
                ++num;
            }
            result = max(result, cnt);
        }
        return result;
    }
};

算法2：带权并查集

在并查集中，用哈希表维护节点间的父子关系，这里注意并查集中的树节点值保存的是 nums 中的元素值，而不是编号。

对于 nums 中的每个数字 i，调用 merge(i, i + 1)，如果 i + 1 在并查集中，则会执行合并。

最终每个连通分量代表一个连续序列，每个连通分量维护一个权值，保存连通分量重的元素数。

注意 根节点的权 _size(_find(x)) 才是有效的，因为查询(路径压缩)时没有更新权，非根节点的权值是错的。

代码 (C++)

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class UnionFindSet {
public:
    UnionFindSet(const vector<int>& nums)
    {
        int n = nums.size();
        _set_num = n;
        for(int i = 0; i < n; ++i)
        {
            _father[nums[i]] = nums[i];
            _size[nums[i]] = 1;
        }
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    int merge(int x, int y)
    {
        // merge 后返回集合大小
        x = _find(x);
        y = _find(y);
        if(x == y) return _size[x];

        // 此时 x, y 是所在树的根
        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
            _size[y] += _size[x];
            --_set_num;
            return _size[y];
        }
        else
        {
            _father[y] = x;
            _size[x] += _size[y];
            if(_rank[x] == _rank[y])
                ++_rank[x];
            --_set_num;
            return _size[x];
        }
    }

    int count(int x)
    {
        // 返回元素 x 是否在并查集中
        return _father.count(x);
    }

    int set_size(int x)
    {
        return _size[_find(x)];
    }

    int set_num()
    {
        return _set_num;
    }

private:
    unordered_map<int, int> _father;
    unordered_map<int, int> _rank;
    unordered_map<int, int> _size; // 集合级的权
    int _set_num;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        UnionFindSet unionfindset(nums);

        int result = 1;
        for(int i: nums)
        {
            if(i != INT_MAX && unionfindset.count(i + 1))
                result = max(result, unionfindset.merge(i, i + 1));
        }
        return result;
    }
};

面试题 17.07. 婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

提示：

1
names.length <= 100000

示例：
输入：names = [“John(15)”,”Jon(12)”,”Chris(13)”,”Kris(4)”,”Christopher(19)”], synonyms = [“(Jon,John)”,”(John,Johnny)”,”(Chris,Kris)”,”(Chris,Christopher)”]
输出：[“John(27)”,”Chris(36)”]

算法：带权并查集

集合级别的权：姓名。合并时选取根的标准将按秩合并改为：谁的姓名小，谁作为根。

代码 (C++)

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class UnionFindSet
{
public:
    UnionFindSet(const unordered_map<string, int>& mapping)
    {
        int n = mapping.size();
        _father = vector<int>(n, -1);
        _name = vector<string>(n, "");
        for(int i = 0; i < n; ++i)
            _father[i] = i;
        for(const auto &item: mapping)
        {
            const string &name = item.first;
            int id = item.second;
            _name[id] = name;
        }
    }

    bool same(int a, int b)
    {
        return _find(a) == _find(b);
    }

    void merge(int a, int b)
    {
        int x = _find(a);
        int y = _find(b);
        if(x == y)
            return ;
        if(_name[x] < _name[y])
            _father[y] = x;
        else
            _father[x] = y;
    }

    string query(int id)
    {
        int root = _find(id);
        return _name[root];
    }

private:
    vector<string> _name;
    vector<int> _father;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        unordered_map<string, int> mapping; // 有本质同名记录的名字对应的 id
        int id = 0;
        for(const string& item: synonyms)
        {
            // item 示例
            // "(Jon,John)"
            int n = item.size();
            int left = 1;
            int right = left + 1;
            while(right < n - 1 && item[right] != ',')
                ++right;
            string name1 = item.substr(left, right - left);
            string name2 = item.substr(right + 1, n - 1 - (right + 1));
            if(mapping.count(name1) == 0)
                mapping[name1] = id++;
            if(mapping.count(name2) == 0)
                mapping[name2] = id++;
        }
        unordered_map<string, int> records;
        UnionFindSet unionfindset(mapping);
        for(const string& item: synonyms)
        {
            // item 示例
            // "(Jon,John)"
            int n = item.size();
            int left = 1;
            int right = left + 1;
            while(right < n - 1 && item[right] != ',')
                ++right;
            string name1 = item.substr(left, right - left);
            string name2 = item.substr(right + 1, n - 1 - (right + 1));
            int id1 = mapping[name1];
            int id2 = mapping[name2];
            unionfindset.merge(id1, id2);
        }
        for(const string& item: names)
        {
            // item 示例
            // "John(15)"
            int n = item.size();
            int left = 0;
            int right = left + 1;
            while(right < n && item[right] != '(')
                ++right;
            string name = item.substr(left, right - left);
            string num = item.substr(right + 1, n - 1 - (right + 1));
            int cnt;
            stringstream ss;
            ss << num;
            ss >> cnt;
            if(mapping.count(name) == 0) // 无本质相同姓名记录
                records[name] += cnt;
            else
            {
                string base_name = unionfindset.query(mapping[name]);
                records[base_name] += cnt;
            }
        }
        vector<string> result;
        for(const auto &item: records)
        {
            const string &name = item.first;
            int cnt = item.second;
            result.push_back(name + '(' + to_string(cnt) + ')');
        }
        return result;
    }
};

952. 按公因数计算最大组件大小

带权并查集 + 素数筛，题解参考：力扣952-按公因数计算最大组件大小。

1632. 矩阵转换后的秩

带权并查集 + 拓扑排序，用集合的代表元建图处理集合级信息，题解参考：用并查集中各集合的代表元建图，处理集合级信息。

928. 尽量减少恶意软件的传播 II

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

提示：

1
2
3
4
5
6
7
8
9
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] 是 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
 initial 中每个整数都不同

示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0

示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1

示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1

算法：带权并查集

用并查集维护这 N 个节点，其中包含两种集合级的信息，一个是连通分量元素个数，另一个是连通分量中的病毒个数。

枚举所有的节点对 $(i, j)$，如果是图中的边，且 $i, j$ 均不是初始时的污染节点，则在并查集中 merge(i, j)。

然后枚举每个初始时的污染节点 $i$，然后枚举图中 $i$ 的每条边 $(i, j)$，修改 $j$ 所在连通分量的代表病毒个数的那个权值，将其加一。

枚举每个初始时的病毒节点 $i$，该节点可能与并查集中的多个集合相连。由于只能删除一个节点，因此我们就只要与 $i$ 相连且代表病毒个数的权值为一的连通分量，这些连通分量重的元素是将 $i$ 删除后可以减少感染的节点。

代码 (C++)

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _father.assign(n, -1);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
        _rank.assign(n, 0);
        _weight.assign(n, 1);
        _label.assign(n, 0);
    }

    int get_weight(int x)
    {
        return _weight[_find(x)];
    }

    void set_label(int x)
    {
        ++_label[_find(x)];
    }

    int get_label(int x)
    {
        return _label[_find(x)];
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y)
            return;

        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
            _weight[y] += _weight[x];
        }
        else
        {
            _father[y] = x;
            _weight[x] += _weight[y];
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<int> _weight;
    vector<int> _label;

    int _find(int x)
    {
        if(x == _father[x])
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        unordered_set<int> setting(initial.begin(), initial.end());
        UnionFindSet unionfindset(n);
        for(int i = 0; i < n - 1; ++i)
        {
            for(int j = i + 1; j < n; ++j)
            {
                if(graph[i][j] == 1 && setting.count(i) == 0 && setting.count(j) == 0)
                {
                    unionfindset.merge(i, j);
                }
            }
        }
        for(int i: initial)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i == j) 
                    continue;
                if(setting.count(j) > 0)
                    continue;
                if(graph[i][j] == 0)
                    continue;
                unionfindset.set_label(j);
            }
        }

        int ans = -1;
        int max_cand = -1;
        for(int i: initial)
        {
            int cand = 0;
            for(int j = 0; j < n; ++j)
            {
                if(i == j)  
                    continue;
                if(setting.count(j) > 0) 
                    continue;
                if(graph[i][j] == 0)
                    continue;
                if(unionfindset.get_label(j) == 1)
                {
                    int cc = unionfindset.get_weight(j);
                    cand += cc;
                }

            }
            if(cand > max_cand)
            {
                max_cand = cand;
                ans = i;
            }
            else if(cand == max_cand && i < ans)
                ans = i;
        }
        return ans;
    }
};
Share