首先上一道leetcode的题目：https://leetcode-cn.com/problems/satisfiability-of-equality-equations/
这道题我们看到之后很容易的思路就是先把所有相等的关系找个数据结构保存下来，然后依次判断不等式的两方是否同时存在于刚才的结构中。
这个过程的第一步就是并集，把相关的数据放在一个集合中，第二步就是查找，在这个集合中查找相关性是否成立，这个查找的过程中可以进行一定的优化，也就是并集查找中的路径压缩。这里推荐这篇博客：https://blog.csdn.net/liujian20150808/article/details/50848646
算法
用集合中的某个元素来代表这个集合，该元素称为集合的代表元。
一个集合内的所有元素组织成以代表元为根的树形结构。
对于每一个元素 parent[x]指向x在树形结构上的父亲节点。如果x是根节点，则令parent[x] = x。
对于查找操作，假设需要确定x所在的的集合，也就是确定集合的代表元。可以沿着parent[x]不断在树形结构中向上移动，直到到达根节点。
1
| 判断两个元素是否属于同一集合，只需要看他们的代表元是否相同即可。
|
路径压缩
1
2
3
| 为了加快查找速度，查找时将x到根节点路径上的所有点的parent设为根节点，该优化方法称为压缩路径。
使用该优化后，平均复杂度可视为Ackerman函数的反函数，实际应用中可粗略认为其是一个常数。
|
代码
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
|
var find = function (parent, index) {
index = index.charCodeAt() - 97;
while(parent[index] != index) {
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
var union = function (parent, index1, index2) {
parent[find(parent, index1)] = find(parent, index2);
}
var equationsPossible = function(equations) {
let parent = [];
for (let i = 0; i < 26; i++) {
parent[i] = i;
}
for (let i = 0; i < equations.length; i++) {
if (equations[i].indexOf('==') == 1) {
const variables = equations[i].split('==');
union(parent, variables[0], variables[1]);
}
}
for (let i = 0; i < equations.length; i++) {
if (equations[i].indexOf('!=') == 1) {
const variables = equations[i].split('!=');
if (find(parent, variables[0]) == find(parent, variables[1])) {
return false
}
}
}
return true;
};
|
使用场景
从我目前的理解来看，并查集适用于将一组数据分成一块块相互连接的数据的情况，比如上面这种，根据等式关系将所有数据划分为一块块数据集，每一块数据集内部的数据都是相等的。
例1
https://leetcode-cn.com/problems/redundant-connection/
在一棵树中，边的数量比节点的数量少 11。如果一棵树有 NN 个节点，则这棵树有 N-1N−1 条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 NN。
树是一个连通且无环的无向图，在树中多了一条附加的边之后就会出现环，因此附加的边即为导致环出现的边。
可以通过并查集寻找附加的边。初始时，每个节点都属于不同的连通分量。遍历每一条边，判断这条边连接的两个顶点是否属于相同的连通分量。
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
| var findRedundantConnection = function(edges) {
const nodesCount = edges.length;
const parent = new Array(nodesCount + 1).fill(0).map((value, index) => index);
for (let i = 0; i < nodesCount; i++) {
const edge = edges[i];
const node1 = edge[0], node2 = edge[1];
if (find(parent, node1) != find(parent, node2)) {
union(parent, node1, node2);
} else {
return edge;
}
}
return [0];
};
const union = (parent, index1, index2) => {
parent[find(parent, index1)] = find(parent, index2);
}
const find = (parent, index) => {
while(parent[index] !== index) {
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
|
例2
https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/
根据可以移除石头的规则：如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。可以发现：一定可以把一个连通图里的所有顶点根据这个规则删到只剩下一个顶点。
为什么这么说呢？既然这些顶点在一个连通图里，可以通过遍历的方式（深度优先遍历或者广度优先遍历）遍历到这个连通图的所有顶点。那么就可以按照遍历的方式 逆向 移除石头，最后只剩下一块石头。所以：最多可以移除的石头的个数 = 所有石头的个数 - 连通分量的个数。
题目没有让我们给出具体移除石头的方案，可以考虑使用并查集。
并查集里如何区分横纵坐标
然而会遇到这样一个问题：石头的位置是「有序数对（二维）」，并查集的底层是「一维数组」，我们在并查集里应该如何区分横纵坐标呢？
，可以把其中一个坐标 映射 到另一个与 [0, 10000] 不重合的区间，可以的做法是把横坐标全部减去 10001 或者全部加上 10001
在并查集里我们需要维护连通分量的个数，新创建顶点的时候连通分量加 11；合并不在同一个连通分量中的两个并查集的时候，连通分量减 11。
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
| var removeStones = function(stones) {
const parent = new Map();
let count = 0;
const find = function(x) {
if (!parent.has(x)) {
parent.set(x, x);
count++;
}
if (parent.get(x) != x) {
parent.set(x, find(parent.get(x)));
}
return parent.get(x);
}
const union = function(x, y) {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
parent.set(rootX, rootY);
count--;
}
}
stones.forEach((stone) => {
union(stone[0] + 10001, stone[1]);
})
return stones.length - count;
};
|