C++ 按秩合并和路径压缩的并查集算法

并查集算法负责维护不同的集合，并提供操作来验证是否属于一个集合以及将集合合并。它熟练处理合并和查找操作，这两者对于维护元素之间的当前连接信息至关重要。

语法

为了确保清晰，让我们首先理解即将在下面的代码示例中使用的方法的语法。

// Method to perform Union operation
void Union(int x, int y);

// Method to find the representative element of a set
int Find(int x);

步骤

Union-Find算法由两个基本操作构成——Union和Find。Union操作将两个集合合并，而Find操作确定一个集合的代表元素。通过反复应用Union和Find操作，我们可以构建一个高效的Union-Find数据结构。

按秩合并

按秩合并技术用于优化Union操作，确保较小的树始终连接到较大树的根节点。这种方法可以防止树变得过于不平衡，从而导致Find操作低效。

按秩合并的算法如下：

找到包含元素x和y的集合的代表元素（根元素）。
如果两个代表元素相同，则返回。
如果x的代表元素的秩大于y的代表元素的秩，使y的代表元素指向x的代表元素，并更新x的代表元素的秩。
否则，使x的代表元素指向y的代表元素，并在必要时更新y的代表元素的秩。

路径压缩

路径压缩是另一种优化技术，可以减小Union-Find数据结构中树的高度。它通过在Find操作期间平坦化路径，使得后续操作的路径更短。

路径压缩的算法如下：
找到包含元素x的集合的代表元素（根元素）。
在从x到其代表元素的路径上遍历时，使每个经过的元素直接指向代表元素。

方法

现在我们已经了解了按秩合并和路径压缩的基本概念，让我们讨论两种在C++中实现Union-Find算法的不同方法。

方法1：基于数组的实现

在这种方法中，我们将每个集合表示为一个数组。每个索引处的值表示该元素的父节点。最初，每个元素都是自己的父节点，表示它是其集合的代表元素。

步骤

让我们开始初始化parent数组的过程。每个元素将被分配为自己的父节点。
使用路径压缩实现Find操作。
使用按秩合并实现Union操作。

示例

#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