1 基本介紹

并查集是一種用來判斷兩個元素之間是否有關系的集合。
它的基本思想為：對于兩個元素，如果他們之間有關系，則將其連接，以此形成一顆樹。
對于任意兩個節點，如果它們有相同的根節點，則它們之間有關系。

2. 建立步驟

給定n個點，以及m個關系。

1. 初始狀態

將每個節點的根節點都指向自己

for (int i = 0; i < n; i++) {
	pre[i] = i;
}

2. 建立關系

對于給定的兩個節點，我們發現，如果要連接兩個節點所在的樹，只能改變根節點。所以，我們先構建方法尋找根節點，再將一顆樹的根節點連接到另一棵樹的根節點上。

int find(int x) {
//1. 遞歸方式
	return pre[x] == x ? x : find(pre[x])
//2. 非遞歸
	while(pre[x]^x) x = pre[x];
	return x;
}

連接函數

void merge(int x, int y) {
	x = find(x), y = find(y);
	pre[x] = y;
}

例題分析

來源：洛谷P3367

1. 并查集（無優化）

#include <iostream>
using namespace std;
const int N = 10e5 + 9;
int pre[N];
int find(int x) {
	while (pre[x] ^ x) x = pre[x];
	return x;
}
void merge(int x, int y) {
	x = find(x), y = find(y);
	pre[x] = y;
}
void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < N; i++) pre[i] = i;
	while (m--) {
		int z, x, y;
		cin >> z >> x >> y;
		if (z == 1) {
			merge(x, y);
		} else {
			cout << (find(x) == find(y) ? 'Y' : 'N') << "\n";
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while (_--) solve();
	return 0;
}

2. 路徑壓縮

當我們每一次查找x的根節點的時候，順便將x的父節點的根節點也變成根節點，使得生成的樹的形狀又矮又胖。
只需要修改find函數

int find(int x) {
	return pre[x] == x ? x : pre[x] = find(pre[x]);
}

或者為使用兩次while循環來改變。

3. 按秩合并

由上面的分析我們知道，如果是將一顆小樹附加到一顆大樹上面，那么在查找的過程中的復雜度會降低，以此，我們構建一個rank數組，初始值都為1，它記錄這棵樹的層數（只有根節點的數有效，畢竟我們只連接根節點）
注意，當我們使用按秩合并的時候，我們在查找的時候就不能進行路徑壓縮（這樣會導致秩不斷在改變，我嘗試了一下一起使用，效果反而不如單個使用）。
修改的merge函數為：

void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (rnk[x] >= rnk[y]) pre[y] = x, rnk[x]++;
	else
		pre[y] = x, rnk[y]++;
}

4. 按大小合并

和秩一樣，當一顆較小的樹合并到另一棵較大的樹的時候，形成的樹會變得矮胖。因此，創建一個siz數組來儲存每棵樹的大小，初始值為1。和上面一樣，只需要修改為：

void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (siz[x] >= siz[y]) pre[y] = x, siz[x] += siz[y];
	else
		pre[y] = x, siz[y] += siz[x];
}