含集合级信息的并查集

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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