并查集优化
1.1 路径压缩
在基本的并查集实现中，查找操作可能会导致较长的查找链，特别是在树的高度较大时。路径压缩是一种优化技术，它在查找过程中将路径上的所有节点直接连接到根节点，从而减少后续查找的时间。
路径压缩的概念
路径压缩的核心思想是：在查找某个元素的根节点后，将路径上的所有节点都直接指向根节点，形成一个扁平的树结构。
路径压缩的实现方法
路径压缩可以通过修改查找函数来实现：
// 带路径压缩的查找操作
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]); // 路径压缩
}
}
这个实现在递归返回的过程中，将路径上的每个节点的父节点都设置为根节点。
另一种等价的非递归实现：
// 非递归实现的路径压缩
int find(int x) {
int root = x;
// 找到根节点
while (parent[root] != root) {
root = parent[root];
}
// 路径压缩：将路径上的所有节点直接连接到根节点
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
路径压缩的效果分析
路径压缩极大地提高了查找操作的效率。在最坏情况下，未经优化的并查集查找操作的时间复杂度为O(n)，而使用路径压缩后，平均时间复杂度接近O(1)。
路径压缩前后的结构变化示例：
压缩前：
1
/
2
/
3
/
4
压缩后（查找元素4后）：
1
/ | \
2 3 4
1.2 按秩合并
在基本的并查集实现中，合并操作可能会导致树的高度增加，从而增加查找操作的时间。按秩合并是一种优化技术，它在合并两个集合时，总是将较小的树连接到较大的树上，从而控制树的高度。
按秩合并的概念
"秩"可以理解为树的高度或大小。按秩合并的核心思想是：在合并两个集合时，将较小的树（秩较小的树）连接到较大的树（秩较大的树）上，而不是随意选择。
按秩合并的实现方法
按秩合并需要额外维护一个数组来记录每个集合的秩。通常有两种实现方式：
- 按树的高度（rank）合并：
int rank[MAXN]; // 记录每个集合的高度
// 初始化
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0; // 初始高度为0
}
}
// 按高度合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++; // 如果高度相同，则合并后高度加1
}
}
}
- 按树的大小（size）合并：
int size[MAXN]; // 记录每个集合的大小
// 初始化
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1; // 初始大小为1
}
}
// 按大小合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
}
按秩合并的效果分析
按秩合 并可以有效控制树的高度，防止树变得过高。在最坏情况下，未经优化的并查集可能形成一条链，高度为O(n)，而使用按秩合并后，树的高度最多为O(log n)。
按秩合并前后的结构变化示例：
合并前：
集合1： 集合2：
1 4
/ \ / \
2 3 5 6
不使用按秩合并（随意选择）：
1
/ \
2 3
\
4
/ \
5 6
使用按秩合并（假设按大小合并）：
4
/ \
5 6
\
1
/ \
2 3
1.3 完整优化的并查集实现
结合路径压缩和按秩合并的完整并查集实现：
const int MAXN = 10005;
int parent[MAXN];
int rank[MAXN]; // 使用高度作为秩
// 初始化并查集
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 带路径压缩的查找操作
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]); // 路径压缩
}
}
// 按秩合并
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
时间复杂度分析
结合路径压缩和按秩合并的并查集，其操作的平均时间复杂度接近于常数级别。严格来说，时间复杂度是O(α(n))，其中α(n)是阿克曼函数的反函数，这个函数增长极其缓慢，对于任何实际应用中的n值，α(n)的值都不会超过5。
因此，在实际应用中，我们可以认为优化后的并查集操作的时间复杂度接近O(1)，这使得并查集成为解决大规模连通性问题的高效工具。