称为并查集（或不相交集）的算法负责维护不同的集合，并提供操作来验证集合中的成员资格并将集合组合在一起。它熟练地处理并集和查找操作，这对于维护元素之间的当前连接信息至关重要。
语法
为了确保清晰度，让我们首先理解即将在接下来的代码示例中使用的方法的语法。
// 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 的代表的排名。
路径压缩
路径压缩是另一种优化技术，可降低并查数据结构中树的高度。它的目的是在查找操作期间压平路径，从而为后续操作提供更短的路径。
-
路径压缩的算法如下 -
-
查找包含元素 x 的集合的代表（根元素）。
-
在遍历从x到其代表的路径时，使每个访问过的元素直接指向代表。
方法
现在我们已经了解了按等级并集和路径压缩的基本概念，让我们讨论在 C++ 中实现并查算法的两种不同方法。
方法一：基于数组的实现
在这种方法中，我们将每个集合表示为一个数组。每个索引处的值代表元素的父元素。最初，每个元素都是其自己的父元素，表明它是其集合的代表。
算法
-
让我们开始父数组的初始化过程。每个元素都将被分配其自己的父元素。
-
使用路径压缩实现查找操作。
-
使用 Union by Rank 实现 Union 运算。
示例
#include
#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[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
