TA Can Do What & why learning

what

并查集主要是解決連通塊的問題，例如對于上面的這個由5個村子若干條路構成的簡易地圖，如果問你1----->5是否是連通的，顯然是的，那如果問你3——>5是否連通，顯然是false，因為沒有任何一條路能從3指向5，這不是很簡單嗎

why

那我們需要并查集干嘛？

好問題 如果這個圖如果需要你自己構造而不是直接給你（動態構造集合關系），你很難或者說沒法直接通過給的數據去畫出每一個圖的時候，并查集就能幫助我們迅速判斷是否連通，而往往算法競賽中的題目都是動態構造的（后面會附上例題），所以學習并查集是很有必要的，不然的話很大概率會超時
傳統方式：
假設你有 100 萬個村莊，每次新增一條路（動態添加邊），如果每次都用 DFS/BFS 重新遍歷整個圖來判斷兩個村莊是否連通，時間復雜度會高達 O (N)，效率極低。而并查集的find和union操作經過路徑壓縮和按秩合并優化后，時間復雜度幾乎是O（1）

原理和結構

我們需要知道兩個概念父節點和祖先，有一點像二叉樹章節里的但又不太一樣，尤其是對于祖先這個概念，
祖先代表的是：某一個節點不斷去尋找他的父節點（遞歸），直到某一個節點的父節點是他本身（出口）

題外話：我在學習的時候感覺有點像 二叉樹章節里面的 求最大深度問題，其實后來我想了一下是很正常的
畢竟樹從某種意義上來說是特殊的圖

言歸正傳：我們用一個pre數組來保存每個節點的父親，我們的數組如下圖所示，這里特意需要說的就是 1的父親是他本身，所以1對應pre數組里頭存儲的父節點就是1

這句話怎么來理解呢：
其實可以把1看做是上面這個集合（1,2,4,5）的代表元素，也就是根節點，打個比方來說，這個1就是這個集合(家族)里面最年長的，就像家族的 “掌門人” 一樣，沒有比他更年長的父親了，所以他的父親就是他自己。
成員 1 作為這個家族的代表元素（根節點），就像是整個家族的源頭，其他成員都是從他這里 “衍生” 出來的，就像一棵大樹，成員 1 是樹干最頂端的那個起始點，其他成員是從樹干上長出來的樹枝和樹葉。

通過上面的例子大家應該會有一個比較基礎的了解，但是在一開始每一個節點都是跟自己是一個連通關系（即指向自身）

就比如在添加1-2這條邊的時候，我們就會讓2的祖先指向1，在添加2-4這條邊的時候，我們就需要注意，打個比方來說
由于2的“錢”已經交給1了，4想要找2要錢是找不到的，只能去找1了，體現在圖中就是讓4的祖先指向1，
總結來說就是：對于任何非根節點的相連都必須轉換成它們各自的根節點相連
那現在我們已經可以用個構建的這個表來判斷節點之間是否連通了，就比如1一直找，找到他的祖先是4，這個時間復雜度是O（N）的，但是這只是一次查詢的情況如果有n次查詢，那么時間復雜度就是O（n方），
那么有沒有辦法去優化它呢？
其實是有的——路徑壓縮（沒學之前聽著恐怖 其實是紙老虎）

路徑壓縮

我對于路徑壓縮的理解（可能不完全準確哈）：
就是好比你是一個失憶的人，現在知道四個地方，A B C D，你通過不斷探索知道了A是經過B C 能走到D的，也就是說你現在知道A到D是連通的，但是每過一段時間 如果一個人問你，你都需要重新走一遍，路徑壓縮好比就是，你用筆記本記下來了，A到D是通的并且D是終點，（這就引出了路徑壓縮的核心思想：通過直接記錄最終結果（根節點），避免重復計算路徑）
同理B,C到D也是通的，我們這里并不關心，A怎么到D，只關心從A能不能到D

壓縮完成就是這個情況：

本質：
犧牲空間（存儲父指針）換取時間（快速查詢）
將樹的高度 “壓扁”，使得后續的find操作時間復雜度接近 O (1)
這里壓扁的是啥？不就是我們尋找的路徑path嗎

例題講解

題解

題目說的很直白就是讓你用并查集的思路，其中有一個flag Z當它變化的時候，分別對應兩種操作：1.合并（merge）2.判斷（isCon）

solution 1（50分）

還有50%的測試點，數據非常大，即便關閉同步流，還是超時了嗎，還是做不到嗎，哈基霜你這家伙…

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int pre[maxn];//存儲父節點int root(int x)
{return pre[x] == x ? x : pre[x] = root(pre[x]);
}
//一切操作都在根上
void Merge(int x, int y)
{pre[root(x)] = root(y);
}bool isCon(int x, int y)
{return root(x) == root(y);
}void init(int N)
{for (int i = 1; i <= N; ++i) pre[i] = i;
}signed main()
{ios::sync_with_stdio(0);int N, M;cin >> N >> M;init(N);while (M--){int Z, X, Y;cin >> Z >> X >> Y;if (Z == 1)Merge(X, Y);else if (Z == 2)printf("%c\n", isCon(X, Y) ? 'Y' : 'N');}return 0;
}

solution 2（100分）

之前代碼僅實現路徑壓縮，未結合按樹高或者大小合并，在數據量大 時，樹可能因合并順序不當變得高度很高，導致find操作時間復雜度退化為接近O(n)，最終超時。而當前代碼通過兩種優化，將單次操作的時間復雜度優化至幾乎常數級

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 9;
int pre[maxn];// 存儲父節點
int siz[maxn];// 存儲集合大小（模擬秩）// 初始化并查集
void init(int N) {for (int i = 1; i <= N; ++i) {pre[i] = i;siz[i] = 1; // 初始時每個集合大小為 1}
}// 查找根節點并路徑壓縮
int root(int x) {return pre[x] == x ? x : pre[x] = root(pre[x]);
}// 合并兩個集合，按集合大小（秩）優化
void Merge(int x, int y) {int rx = root(x);int ry = root(y);if (rx == ry) return; // 已在同一集合，無需合并// 保證將較小集合合并到較大集合if (siz[rx] > siz[ry]) swap(rx, ry); pre[rx] = ry;if (siz[rx] == siz[ry]) siz[ry]++; // 若大小相等，合并后新集合秩+1
}// 判斷兩個元素是否連通
bool isCon(int x, int y) {return root(x) == root(y);
}signed main() {ios::sync_with_stdio(0);int N, M;cin >> N >> M;init(N);while (M--) {int Z, X, Y;cin >> Z >> X >> Y;if (Z == 1) {Merge(X, Y);} else if (Z == 2) {printf("%c\n", isCon(X, Y) ? 'Y' : 'N');}}return 0;
}

這就引出了下面的優化方法按秩合并和啟發式合并

按秩(樹高)合并

在這之前啊，我們是不是通過解決 斜樹查找退化成鏈表的問題 學習過平衡二叉樹的概念，
這個其實跟這里的按秩合并非常像，解決的問題也很像

比如說上面這張圖，如果新增的邊是4->3,
那拿3這個節點舉例，那他走到根只需要兩步，那如果是3->4,那就需要走3步，根節點向右傾斜了

對于一棵樹 我們更希望它變成 矮墩墩 而不是長竹竿，所以就需要我們添加邊的時候就需要進行比較 矮的指向高的

按大小合并

跟上面跟類似用小的集合指向大的集合 也就是比較少的點會多走一步

void Merge(int x, int y) {int rx = root(x);int ry = root(y);if (rx == ry) return; // 已在同一集合，無需合并// 保證將較小集合合并到較大集合if (siz[rx] > siz[ry]) swap(rx, ry); pre[rx] = ry;if (siz[rx] == siz[ry]) siz[ry]++; // 若大小相等，合并后新集合秩+1
}