前言：
前面我们已经学习了简单的数据结构，包括栈与队列、二叉树、红黑树等等，今天我们继续数据结构的学习，但是难度上会逐渐增大，在高阶数据结构中我们要学习的重点是图等
目录
并查集的原理
并查集的基本操作
实现方式
C++实现
C语言实现
并查集的原理
并查集（Disjoint-Set Data Structure）是一种用于管理集合的高效数据结构，特别适用于处理“动态连接”的问题，即动态地合并集合或查询两个元素是否属于同一个集合。并查集在计算机科学中有着广泛的应用，如用于解决最小生成树问题（Prim算法和Kruskal算法）、解决网络连通性问题、解决图论中的问题等。
并查集的基本操作
并查集主要支持以下三种基本操作：
- 查找（Find）：确定一个元素属于哪个集合。
- 合并（Union）：将两个集合合并为一个集合。
- 初始化（Init）：为每个元素创建一个独立的集合。
实现方式
并查集有两种常见的实现方式：路径压缩和按秩合并。
- 路径压缩：在查找操作中，将查找路径上的所有节点的父节点直接指向根节点，以减少查找路径的深度。
- 按秩合并：在合并操作中，将秩较小的集合合并到秩较大的集合中，以减少树的高度。
C++实现
#include <iostream>
#include <vector>class UnionFind {
private:std::vector<int> parent;std::vector<int> rank;public:UnionFind(int n) : parent(n), rank(n) {for (int i = 0; i < n; ++i) {parent[i] = i;rank[i] = 1;}}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}void unite(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) return;if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX] += 1;}}bool connected(int x, int y) {return find(x) == find(y);}
};int main() {int n, m;std::cin >> n >> m;UnionFind uf(n);for (int i = 0; i < m; ++i) {int a, b;std::cin >> a >> b;uf.unite(a - 1, b - 1); // 转换为0-based索引}for (int i = 0; i < m; ++i) {int a, b;std::cin >> a >> b;std::cout << (uf.connected(a - 1, b - 1) ? "YES" : "NO") << std::endl;}return 0;
}C语言实现
#include <stdio.h>
#include <stdlib.h>typedef struct {int parent[10001];int rank[10001];
} UnionFind;void init(UnionFind *uf, int n) {for (int i = 0; i <= n; ++i) {uf->parent[i] = i;uf->rank[i] = 1;}
}int find(UnionFind *uf, int x) {if (uf->parent[x] != x) {uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩}return uf->parent[x];
}void unite(UnionFind *uf, int x, int y) {int rootX = find(uf, x);int rootY = find(uf, y);if (rootX == rootY) return;if (uf->rank[rootX] > uf->rank[rootY]) {uf->parent[rootY] = rootX;} else if (uf->rank[rootX] < uf->rank[rootY]) {uf->parent[rootX] = rootY;} else {uf->parent[rootY] = rootX;uf->rank[rootX] += 1;}
}int main() {int n, m;scanf("%d %d", &n, &m);UnionFind uf;init(&uf, n);for (int i = 0; i < m; ++i) {int a, b;scanf("%d %d", &a, &b);unite(&uf, a - 1, b - 1); // 转换为0-based索引}for (int i = 0; i < m; ++i) {int a, b;scanf("%d %d", &a, &b);if (find(&uf, a - 1) == find(&uf, b - 1)) {printf("YES\\n");} else {printf("NO\\n");}}return 0;
}通过上述C++和C语言的实现，我们可以看到并查集的基本操作和逻辑在不同语言中的实现方式。这两种语言的实现都遵循了并查集的核心思想，即通过查找和合并操作来管理集合，以高效地处理动态连接问题。