称为并查集（或不相交集）的算法负责维护不同的集合，并提供操作来验证集合中的成员资格并将集合组合在一起。它熟练地处理并集和查找操作，这对于维护元素之间的当前连接信息至关重要。
语法
为了确保清晰度，让我们首先理解即将在接下来的代码示例中使用的方法的语法。
// Method to perform Union operation
void Union(int x, int y);
// Method to find the representative element of a set
int Find(int x);
算法
并查算法由两个基本操作组成 - 并集和查找。并集运算合并两个集合，查找运算确定集合的代表元素。通过迭代应用并查运算，我们可以构建高效的并查数据结构。
按等级联合
按等级联合技术用于通过确保较小的树始终附加到较大的树的根来优化联合操作。这种方法可以防止树变得过于不平衡，从而导致查找操作效率低下。
按等级联合的算法如下 -
查找包含元素 x 和 y 的集合的代表（根元素）。
如果代表相同，则返回。
如果x的代表的等级大于y的代表的等级，则使y的代表指向x的代表，并更新x的代表的等级。
否则，使 x 的代表指向 y 的代表，并在必要时更新 y 的代表的排名。
路径压缩
路径压缩是另一种优化技术，可降低并查数据结构中树的高度。它的目的是在查找操作期间压平路径，从而为后续操作提供更短的路径。
方法
现在我们已经了解了按等级并集和路径压缩的基本概念，让我们讨论在 C++ 中实现并查算法的两种不同方法。
方法一：基于数组的实现
在这种方法中，我们将每个集合表示为一个数组。每个索引处的值代表元素的父元素。最初，每个元素都是其自己的父元素，表明它是其集合的代表。
算法
示例
#include <iostream>
#define MAX_SIZE 100
// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];
void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
void Union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
// Union by rank
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
int main() {
// Usage example
makeSet(10); // Assuming 10 elements in the set
Union(1, 2);
Union(3, 4);
// Print parent array
for (int i = 0; i < 10; i++) {
std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
}
return 0;
}
输出
Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9
方法 2：基于树的实现
为了描述我们研究中的集合，我们使用了基于树的方法。组中的每个项目都与其各自的父节点关联，同时我们指定根节点来表示该特定集合。
算法
示例
#include <iostream>
#define MAX_SIZE 100
// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];
void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
void Union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
// Union by rank
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
int main() {
// Usage example
makeSet(10); // Assuming 10 elements in the set
Union(1, 2);
Union(3, 4);
// Print parent array
for (int i = 0; i < 10; i++) {
std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
}
return 0;
}
输出
Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9
结论
总而言之，按等级并集和路径压缩是并查算法中的关键技术。它们分别优化了
.........................................................