數據結構——並查集

數據結構教程：並查集（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的上界。