Graph Theory & DSU

並查集是一種樹狀結構
處理集合問題，主要有以下兩個操作

查詢元素所在集合(find)
合併兩個集合(union)

並查集只需要用一個長度為 \(n\) 的陣列即可，
陣列內第 \(i\) 格存的值為第 \(i\) 個節點的父節點編號

 int f[n];
 
f[3] // 節點 3 的父節點編號
f[5] // 節點 5 的父節點編號

根節點

如果一個點為根節點，他的父節點為自己 (f[x] == x)

以下圖為例， 1、6 為根節點

判斷集合

定義兩個相異元素如果屬於同一個集合，則兩個元素會在並查集的同一棵樹上

如何判斷在同一棵樹上?

find 函數

find 函數會找到某個節點 x 的根節點

如果兩個點的根節點相同，代表在同一棵樹上，
也就是屬於同一個集合

find(x) == find(y);

則 x 與 y 所屬同一個集合

find 函數

 int find(int x){
    if ( x == f[x] )    // 如果當前節點為 f[x]==x
        return x;       // 則為根節點
    return find(f[x]);  
}

union 函數

如果有兩個節點 a, b 所在的集合想要合併成一個集合

做法為找到兩集合的根節點
將其中一個集合的根節點連到另外一個的根節點

以下圖為例

union 函數

合併 2 所在的的集合跟 7 所在的集合
則先找到 2 的根節點 =1, 7 的根節點 =6
將其中一個根節點的父節點設為另一個根節點

則 7 所在的集合所有元素的根節點都會變成 1

union 函數

這邊合併的函數名稱不使用
因為 union 為關鍵字 (撞名內建函數）
因此名稱改用 merge

 void merge(int x,int y)  // 合併 x, y 所在集合
{
    x = find(x);    // x 找到其根節點
    y = find(y);    // y 找到其根節點
    
    if(x != y)      // 如果 x,y 原本就屬於同一個集合則不需合併
        f[y]=x;     // 將其中一個根節點連到另一個
}

初始化

一開始每個元素皆屬於屬於不同集合
因此會將節點指向自己，因為這時候每個元素都是根節點

 int f[N];
void init(){
    for(int i=0;i<n;i++)
        f[i] = i;    // 將每個元素根節點設為自己
    //或者也可以使用 iota(f, f+n, 0); 代替迴圈
}

完整程式碼

 void init(){
    for(int i=0;i<n;i++) 
        f[i]=i;
}
int find(int x){
    if ( x == f[x] )    // 如果當前節點為 f[x]==x
        return x;       // 則為根節點
    return find(f[x]);  // 否則繼續往父節點方向找根節點
}
void merge(int x,int y){
    x=find(x), y=find(y);
    if(x!=y)    f[y]=x;
}

優化

在最差的情況下
合併後的集合的樹形有可能會變成一條鏈

\(\rightarrow\) find() 複雜度退化成 \(O(N)\)

以上圖為例，find(5) 需要跑完全部節點才能找到根節點

啟發式合併

Union by Rank

記錄每棵樹的大小，並在每次合併的時候，將小的集合合併到大的集合。

做法

宣告 sz 陣列，紀錄每個節點的為根的集合大小

在初始化的時候將每個集合大小 sz[i] 都設成 1

 void init(){
    for(int i = 0; i < n; i++){
        f[i] = i;
        sz[i] = 1;
    }
}

當遇到合併操作時，將兩個集合合併成一個時

把小的集合往大的集合合併

找到根節點，根節點儲存整個集合的資訊
合併時，把小的集合的資訊加給大的集合

 int f[N], sz[N];
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x==y)    return;
    if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的
    sz[x] += sz[y]; // 把集合 y 的大小加到集合 x
    f[y] = x;
}

分析

如果是原本的做法
假設有 \(n\) 個節點，合併 \(n - 1\) 次
每次合併都由大小為 \(i\) 的合併到大小為 \(1\) 的，樹就會長成最差的情況（鏈）
每次查詢會退化到 \(O(n)\)

分析

合併兩棵樹高不同的樹

兩個不同的集合合併，如果把樹高比較矮的連往比較高的，
合併後的樹高不會改變

而如果合併的兩個集合樹高相同，
或者高的往矮的合併，則合併後樹高會+1

每次把小的合併到大的方法，
稱之為啟發式合併

使用此方法的合併的樹，在最差情況下
為每次合併時，兩棵樹的樹高都相同

在樹高相同的情況下，會發現每次樹高要 + 1
所需節點數量會變 2 倍

因此 \(n\) 個節點時，使用啟發式合併樹高最高為 \(O(\log n)\)

優化 2

路徑壓縮

在每次 find() 的時候
把經過節點的父節點全部設成根節點

 int find(int x){
    if(f[x] == x)    return x;
    f[x] = find(f[x]);    // 直接將 x 的父節點設成根節點 
    return f[x];
}

呼叫 find(5) 會經過節點 5 4 3 2 1
將中間每個節點的父節點直接設為根節點

 find(5)

\(\rightarrow\)

修改後，之後詢問這些節點時，只需要 O(1) 就會找到根節點

使用啟發式合併+路徑壓縮

能使得單次操作複雜度降到 \(O(\alpha(N))\)
\(O(\alpha(N))\) 趨近於 \(O(1)\)
(\(\alpha( 2^{2^{10^{19729}}} ) = 5\))

因此並查集操作複雜度幾乎是常數時間

完整程式碼

要特別注意合併時，如果兩個元素本來就在同一個集合
要直接回傳，不要重複加到 sz (15行)

 int f[N], sz[N];
void init(){
    for(int i=0;i<n;i++) {
        f[i] = i;  sz[i] = 1;             
    }
}
int find(int x){
    if ( x == f[x] )    // 如果當前節點為 f[x]==x
        return x;       // 則為根節點
    f[x] = find(f[x]);
    return f[x];
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x==y)    return;
    if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的
    sz[x] += sz[y];
    f[y] = x;
}

紀錄集合資訊

如果題目為給定 \(n\) 個元素，每次操作為以下其中一種 :

查詢元素 \(x\) 所在的集合有幾個元素
合併元素 \(x, y\) 分別所在的集合

查詢集合大小

會發現集合大小在做啟發式合併時，
就已經記錄過此資訊 sz[] 了

查詢元素 \(x\) 所在的集合大小只需要找到 \(x\) 的集合的根節點，

 sz[find(x)]

即為所在的集合的大小

如果題目需要求其他資訊，如集合內編號最小/大值等等，
則多為一個陣列 mn[]/mx[] 之類維護每個集合內的資訊

合併集合時，則把兩個集合內的資訊合併

 void merge(int x){
    x = find(x); y = find(y);
    if(x == y)    return;
    if(sz[x] < sz[y])    swap(x, y);
    mn[x] = min(mn[x], mn[y]);
    mx[x] = max(mx[x], mx[y]);
    f[y] = x;
}

相異集合的數量

要找總共有幾個集合，
可以找總共有幾個根節點即可

 int countComponent(){
    int ret = 0;
    for(int i = 0; i < n; i++){
        if(find(i) == i)
            ret++;
    }    
    return ret;
}

並查集在圖論上的意義

給一張 \(n\) 個節點的圖，一開始有 \(m\) 條邊，
接下來有 \(k\) 次操作，每次操作為新增一條邊，
每次操作完輸出最大的連通塊大小 ?

\(n, m, k\le 10^5\)

下圖為例，黑色為一開始的邊，
紅色為依序要加入的邊

當加完 1 號邊之後，最大連通塊大小為 5
當加完 2 號邊之後，最大連通塊大小為 5
當加完 3 號邊之後，最大連通塊大小為 6

連通塊意義

在同一個連通塊中，在並查集中代表在同一個集合。
因此我們可以用並查集維護整張圖誰跟誰連通。

在圖上邊 (x, y) ，相對於 merge(x, y) 操作

並查集應用

Almost-union-find

題序：一個有三種操作的並查集

Union(x, y): 把元素 x , y 分別所在集合合併成同一集合
Move(x, y): 將元素 x 移動到元素 y 所在的集合
Return(x):詢問元素 x 所在的集合內元素個數與元素編號總和

\(1\le n, m\le 10^5\)

可以發現操作 1、3 都是正常的並查集操作
只需要在 merge 的時候維護總和(sum)跟大小(sz)

void merge(int x, int y){
    x = find(x); y = find(y);
    if(x == y)    return;
    if(sz[x] < sz[y])    swap(x, y);
    sz[x] += sz[y];
    num[x] += num[y];
    f[y] = x;
}

而操作 2 比較不一樣，需要做到刪除的操作。

我們可以從兩種情況來看刪除

移除的是葉節點
移除的不是葉節點

1. 移除的是葉節點

在這個情況下，我們只要將根節點記錄大小跟總和的變數把這個節點減掉即可。

2. 移除的不是葉節點

感覺很麻煩，我也不會

捨棄原本的節點

每次詢問，需要回傳集合內元素個數與元素編號總和
把元素 \(x\) 移除，其實只需把 \(x\) 儲存在集合內的資訊移除即可

 void remove(int x){
    root = find(x);
    sz[root]--;
    sum[root] -= x;
}

移除後，原本的節點就不重要了。

加入到新的集合中

要將 \(x\) 加入新集合，可以先給 \(x\) 一個新的編號 \(newid\)
來代表數字 \(x\)

因此我們需要開一個陣列 id[] 維護每個元素當前代表的編號，
並初始化新編號的 sz[], num[]

換新編號 & 合併 x 與 y 的集合

void add(int x){
    f[id[x]] = id[x] = newid++;
    sz[id[x]] = 1;
    sum[id[x]] = x;
}

remove(x);
add(x);
merge(id[x], id[y]);

反著做回來的題目

例題

題序：給一張 \(n\) 個點、\(m\) 條邊的圖，
要做 \(q\) 次操作，每次將一條邊拔掉

求每次拔掉後還有多少塊連通塊？

範圍： \(n, m, q\le 10^6\)

做法

每次刪除後看有幾個連通塊需要花 \(O(n + m)\) 的時間

而我們有 \(q\) 次詢問，很明顯不能這樣做

那這題要怎麼用並查集維護連通塊呢？

做法

如果將刪除變成合併，就跟原本 3-34 的題目類似了?

因此我們可以將操作反過來做

從後往前做，可以發現這樣子操作就從刪除變成合併了！

	struct Edge{
	int u, v, w; // 點 u 連到點 v 並且邊權為 w
	bool operator<(const Edge& rhs){
	return w < rhs.w; //兩條邊比較大小用邊權比較
	}
	};

	Edge graph[200005]; // 宣告 Edge 型態的陣列 graph

	sort(graph,graph+m); // 將邊照大小排序
	int ans=0;

	for(int i=0;i<m;i++){ //>:)
	if(find(graph[i].u) != find(graph[i].v)){ // 如果兩點未聯通
	merge(graph[i].u,graph[i].v); // 將兩點設成同一個集合
	ans += graph[i].w; // 權重加進答案
	if(sz[find(graph[i].u)]==n) break; //當並查集大小等價於樹內點的數量
	}
	}

	cout<<ans<<endl;

	int f[n];

	f[3] // 節點 3 的父節點編號
	f[5] // 節點 5 的父節點編號

	int find(int x){
	if ( x == f[x] ) // 如果當前節點為 f[x]==x
	return x; // 則為根節點
	return find(f[x]);
	}

	void merge(int x,int y) // 合併 x, y 所在集合
	{
	x = find(x); // x 找到其根節點
	y = find(y); // y 找到其根節點

	if(x != y) // 如果 x,y 原本就屬於同一個集合則不需合併
	f[y]=x; // 將其中一個根節點連到另一個
	}

	int f[N];
	void init(){
	for(int i=0;i<n;i++)
	f[i] = i; // 將每個元素根節點設為自己
	//或者也可以使用 iota(f, f+n, 0); 代替迴圈
	}

	void init(){
	for(int i=0;i<n;i++)
	f[i]=i;
	}
	int find(int x){
	if ( x == f[x] ) // 如果當前節點為 f[x]==x
	return x; // 則為根節點
	return find(f[x]); // 否則繼續往父節點方向找根節點
	}
	void merge(int x,int y){
	x=find(x), y=find(y);
	if(x!=y) f[y]=x;
	}

	void init(){
	for(int i = 0; i < n; i++){
	f[i] = i;
	sz[i] = 1;
	}
	}

	int f[N], sz[N];
	void merge(int x, int y) {
	x = find(x), y = find(y);
	if(x==y) return;
	if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的
	sz[x] += sz[y]; // 把集合 y 的大小加到集合 x
	f[y] = x;
	}

	int find(int x){
	if(f[x] == x) return x;
	f[x] = find(f[x]); // 直接將 x 的父節點設成根節點
	return f[x];
	}

	int f[N], sz[N];
	void init(){
	for(int i=0;i<n;i++) {
	f[i] = i; sz[i] = 1;
	}
	}
	int find(int x){
	if ( x == f[x] ) // 如果當前節點為 f[x]==x
	return x; // 則為根節點
	f[x] = find(f[x]);
	return f[x];
	}
	void merge(int x, int y) {
	x = find(x), y = find(y);
	if(x==y) return;
	if(sz[x] < sz[y]) swap(x, y); // 將 x 變成大的
	sz[x] += sz[y];
	f[y] = x;
	}

	void merge(int x){
	x = find(x); y = find(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x, y);
	mn[x] = min(mn[x], mn[y]);
	mx[x] = max(mx[x], mx[y]);
	f[y] = x;
	}

	int countComponent(){
	int ret = 0;
	for(int i = 0; i < n; i++){
	if(find(i) == i)
	ret++;
	}
	return ret;
	}

	void remove(int x){
	root = find(x);
	sz[root]--;
	sum[root] -= x;
	}