对并查集（Disjoint Set Union）的讨论。
1. 并查集基础
并查集用途：给定一堆集合（包括只含有一个元素的集合），快速的合并某些集合，并且能够快速的判断某元素所属的集合。
思路是把每一个集合以多叉树的形式存储，每颗树的根节点都设置为能够唯一的标识它所代表的集合，树中的每个节点都维护着它父节点的信息，得到某元素所属集合的方法就是不断的回溯寻找它的父节点，直到找到根节点，它所属的集合也随之确定。合并操作则只要把其中一颗树根节点的父结点设为另一颗树的根节点即可。
并查集在最开始时所有元素都各自单独为一个集合
1.1 模板
1.1.1 路径压缩优化
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
| int p[n];
for(int i = 1;i<n;i++) p[i] = i;
int find(int x)
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b)
{
p[find(a)] = find(b);
}
class dsu{
public:
vector<int> p;
dsu(int length){
for(int i = 0;i<length;i++) p.push_back(i);
}
int find(int val){
return (val==p[val]?p[val]:p[val] = find(p[val]));
}
void merge(int a, int b){
p[find(a)] = find(b);
}
};
|
1.1.2 额外维护本集合的size值
实现很简单，在合并时把两个集合的size相加即可。
1
2
3
4
5
6
7
8
9
10
11
| int p[n], size[n];
for(int i = 1; i<n; i++) {p[i] = i; size[i]=1;}
void merge(int a, int b){
if(find(a)==find(b)) return;
cnt[find(b)] += cnt[find(a)];
p[find(a)] = find(b);
}
find函数同上
|
1.1.3 额外维护节点与其根的距离(未完成)
1
2
3
4
5
6
7
8
9
10
11
12
| int p[n], d[n];
for(int i = 1;i<n;i++) {p[i] = i; d[i]=0}
int find(int x)
{
if(p[x]!=x)
{
int u = find(p[x]);
d[x]+=d[p[x]];
p[x] = u;
}
return p[x];
}
|
1.2 模板题
1.2.1 合并集合
【题目】
https://www.acwing.com/problem/content/838/
【ac代码】
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
| #include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int find(int val){
if(p[val]!=val) p[val] = find(p[val]);
return p[val];
}
void merge(int a, int b){
p[find(a)] = find(p[b]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++) p[i] = i;
int a, b;
char op[2];
while (m--)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') merge(a,b);
else {
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
|
1.2.2 连通块中点的数量
【题目】
https://www.acwing.com/problem/content/839/
【ac代码】
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
| #include<iostream>
using namespace std;
const int N = 100010;
int p[N];
int cnt[N];
int find(int val){
if(p[val]!=val) p[val] = find(p[val]);
return p[val];
}
void merge(int a, int b){
if(find(a)==find(b)) return;
cnt[find(b)] += cnt[find(a)];
p[find(a)] = find(b);
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++){
p[i] = i;
cnt[i] = 1;
}
char op[2];
int a,b;
while(m--){
string op;
int a, b;
cin >> op;
if (op == "C")
{
cin >> a >> b;
merge(a,b);
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
|
1.2.3 食物链(TODO)
【题目】
https://www.acwing.com/problem/content/242/
【ac代码】
2. 交换字符串中的元素
【题目】
https://leetcode-cn.com/problems/smallest-string-with-swaps/
【解析】
参考了零神的答案。
将字符串的每一个下标看作图中的一个顶点，那么pair数组给出某两个可以交换的下标就相当于在图中将这个两个下标对应的顶点连接起来。又因为存在这样的特性：如果pair数组中某两个下标对有交集【比如(i, j), (j, k)有交集j】，那么这两个下标对中的所有元素都可以互换位置，【如i和k可以交换】。这个特性反映到图中就是任一连通块中所有顶点代表的下标都可以互换。
基于上述讨论，只要我们将pair数组中所有的下标对在图中连接起来，形成几个连通块，并将下标和字符对应起来，然后对这些连通块内部的字符进行排序，最后将排好序字符覆盖到原数组。我们用并查集来做。
【ac代码】
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 dsu{
public:
vector<int> p;
dsu(int length){
for(int i = 0;i<length;i++) p.push_back(i);
}
int find(int val){
return (val==p[val]?p[val]:p[val] = find(p[val]));
}
void merge(int a, int b){
p[find(a)] = find(b);
}
};
class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int length = s.size();
dsu d(length);
for(int i = 0;i<pairs.size();i++) d.merge(pairs[i][0], pairs[i][1]);
unordered_map<int, vector<int>> hash;
for(int i = 0;i<length;i++) hash[d.find(i)].push_back(s[i]);
for(auto t = hash.begin(); t!=hash.end(); t++) sort(t->second.begin(), t->second.end(), greater<int>());
for(int i = 0;i<length;i++){
int root = d.find(i);
s[i] = hash[root].back();
hash[root].pop_back();
}
return s;
}
};
|
3. 冗余连接
【题目】
https://leetcode-cn.com/problems/redundant-connection/
【解析】
前置知识: 树是连通且无环的无向图，边数等于节点数-1 。这道题多了一条冗余的边，则边数等于节点数。
在给所有节点添加边的过程中，如果该边连接的两个点已经是连通的，那么加上这条边必然形成环路，因此这条边一定是冗余的。涉及到判断两点的连通性，可以用并查集来做：每次添加边时判断这条边连接的两个点是否属于同一个集合，如果属于则这条边就是冗余的，否则连接这两个点把它们归到同一个集合中。
【ac代码】
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
| class dsu{
public:
vector<int> p;
dsu(int length){
p.push_back(0);
for(int i = 1;i<=length;i++) p.push_back(i);
}
int find(int x){
return x==p[x]?x:p[x] = find(p[x]);
}
void merge(int a, int b){
p[find(a)] = find(b);
}
};
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int length = edges.size();
dsu d(length);
for(int i = 0;i<length;i++){
int u = edges[i][0];
int v = edges[i][1];
if(d.find(u)==d.find(v)) return {u,v};
d.merge(u,v);
}
return {0,0};
}
};
|
4. 省份数量
【题目】
https://leetcode-cn.com/problems/number-of-provinces/
【解析】
就是在并查集的基础上额外维护一个总集合数量。
【ac代码】
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
| class dsu{
public:
vector<int> p;
int count;
dsu(int length){
for(int i = 0;i<length;i++) p.push_back(i);
count = length;
}
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int a, int b){
if(find(a)==find(b)) return;
p[find(a)] = find(b);
count--;
}
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int length = isConnected.size();
dsu d(length);
for(int i = 0;i<length;i++){
for(int j = 0;j<length;j++){
if(isConnected[i][j]==1) d.merge(i, j);
}
}
return d.count;
}
};
|
5. 执行交换操作后的最小汉明距离
【题目】
https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/
【解析】
因为可交换的坐标对具有传递性，因此利用并查集根据allowedSwaps求出所有连通块，这些连通块中的坐标均可互相交换。然后遍历target数组，每走到一个元素，查看它所属的集合中有没有跟它相同的元素，如果没有，总汉明距离+1；如果有，总汉明距离不变，将该元素在集合中删除。
【ac代码】
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
| class dsu{
public:
vector<int> p;
dsu(int length){
for(int i = 0;i<length;i++) p.push_back(i);
}
int find(int x){
return x==p[x]?x:p[x] = find(p[x]);
}
void merge(int a, int b){
p[find(a)] = find(b);
}
};
class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int length = source.size();
dsu d(length);
for(int i = 0;i<allowedSwaps.size();i++){
d.merge(allowedSwaps[i][0], allowedSwaps[i][1]);
}
unordered_map<int, unordered_map<int, int>> hash;
for(int i = 0;i<length;i++){
hash[d.find(i)][source[i]]++;
}
int count = 0;
for(int i = 0;i<length;i++){
int root = d.find(i);
if(hash[root][target[i]]) hash[root][target[i]]--;
else count++;
}
return count;
}
};
|
6. 等式方程的可满足性
【题目】
https://leetcode-cn.com/problems/satisfiability-of-equality-equations/
【解析】
如果a==b, b==c，那么a==c，即等式具有传递性，那么把a、b和c放到一个集合中。之后碰到不等式时，比如a!=c，因为等号两侧的字母属于同一个集合，说明a和c应该相等，与a!=c矛盾，因此等式方程不可满足。
【ac代码】
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
| class dsu{
public:
vector<int> p;
dsu(){
for(int i = 0;i<26;i++) p.push_back(i);
}
int find(int x){
return x==p[x]?x:p[x] = find(p[x]);
}
void merge(int a, int b){
p[find(a)] = find(b);
}
};
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
dsu d;
int length = equations.size();
for(int i = 0;i<length;i++){
int a = equations[i][0]-'a';
int b = equations[i][3]-'a';
if(equations[i][1]=='=') d.merge(a,b);
}
for(int i = 0;i<length;i++){
int a = equations[i][0]-'a';
int b = equations[i][3]-'a';
if(equations[i][1]=='!' && d.find(a)==d.find(b)) return false;
}
return true;
}
};
|
7. 移除最多的同行或同列石头
【题目】
https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/
【解析】
称石头a与石头b同行或同列为【连通】。如果石头a与石头b连通，石头b与石头c连通，那么石头a和石头c间接连通（即这三个石头可以互相消除——a与c可间接的通过b来互相消除），因此把相互连通的所有石头归到一个集合中。通过画图模拟可以发现，一个包含n块石头的集合中最多可以移除n-1块石头，因此集合的数量就是移除最多的石头后剩余的石头数量。
【ac代码】
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
| class dsu{
public:
vector<int> p;
int size;
dsu(int length){
for(int i = 0;i<length;i++) p.push_back(i);
size = length;
}
int find(int x){
return x==p[x]?x:p[x] = find(p[x]);
}
void merge(int a, int b){
if(find(a)==find(b)) return;
p[find(a)] = find(b);
size--;
}
};
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int length = stones.size();
dsu d(length);
for(int i = 0;i<length;i++){
vector<int> chosen = stones[i];
for(int j = i+1;j<length;j++){
if(stones[j][0]==chosen[0] || stones[j][1] == chosen[1]) d.merge(i, j);
}
}
return length-d.size;
}
};
|