数据结构教程：并查集（Disjoint-Set Union，简称DSU或Union-Find）

一、定义与概念

并查集是一种用于处理不相交集合（Disjoint Sets）合并及查询问题的数据结构。在并查集中，我们维护一系列的元素集合，每个集合由一个代表节点标识，并允许进行两个操作：

1. 查找（Find/Path Compression）：确定给定元素属于哪个集合，以及该集合的代表元素是谁。

2. 合并（Union）：将两个不相交集合合并成一个集合。

二、基本原理与实现

并查集的核心思想是通过“父节点”来表示元素之间的归属关系。每个元素都有一个指向其父节点的指针，同一个集合中的元素最终都会通过链式关系指向同一根节点（即集合的代表元素）。为了提高效率，通常会采用路径压缩和按秩合并等优化策略。

1. 路径压缩：在查找过程中，直接将沿途节点的父节点都指向根节点，使得每次查找操作后的树变得更扁平。

2. 按秩合并：在合并集合时，让秩较小的集合挂接到秩较大的集合下，保持树的高度尽可能低。

三、C++ 示例代码片段

class DisjointSet {private:	vector<int> parent; // 存储每个元素的父节点索引	vector<int> rank; // 存储每个集合的秩public:	DisjointSet(int n) : parent(n), rank(n, 0) {		for (int i = 0; i < n; ++i) {			parent[i] = i;		}	}	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; // 如果x和y已经在同一个集合中，则无需合并		}		// 按秩合并		if (rank[rootX] < rank[rootY]) {			parent[rootX] = rootY;		}		else if (rank[rootX] > rank[rootY]) {			parent[rootY] = rootX;		}		else {			parent[rootY] = rootX;			rank[rootX]++; // 当秩相同时，提升其中一个集合的秩		}	}};// 示例使用int main() {	DisjointSet dsu(10);	dsu.unite(3, 4); // 将元素3和4所在的集合合并	dsu.unite(5, 6);	dsu.unite(7, 8);	assert(dsu.find(3) == dsu.find(4)); // 确保3和4现在在同一集合内	dsu.unite(4, 5); // 合并4所在集合与5所在集合	return 0;}

总结：

并查集是一种简单而强大的数据结构，适用于求解如连通性检查、岛屿数量计算等问题，在网络流算法、图论等领域有着广泛的应用。通过对查找和合并操作进行优化，可以保证在最坏情况下O(logn)的时间复杂度，其中n为元素数量，logn是对数项的小于等于3的上界。