or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Graph Theory & DSU
名詞介紹
(以下內容也都會在資工其他領域學習到
相關用語定義
更多的定義
各種圖的定義
圖之間關係的定義
對於有根樹的定義
Disjoint Set (Union-Find) (DSU)
並查集,又稱不相交集資料結構
並查集是一種樹狀結構
處理集合問題,主要有以下兩個操作
並查集只需要用一個長度為 \(n\) 的陣列即可,
陣列內第 \(i\) 格存的值為第 \(i\) 個節點的父節點編號
根節點
如果一個點為根節點,他的父節點為自己 (f[x] == x)
以下圖為例, 1、6 為根節點

判斷集合
定義兩個相異元素如果屬於同一個集合,則兩個元素會在並查集的同一棵樹上
如何判斷在同一棵樹上?
find 函數
find 函數會找到某個節點 x 的根節點
如果兩個點的根節點相同,代表在同一棵樹上,
也就是屬於同一個集合
則 x 與 y 所屬同一個集合
find 函數
union 函數
如果有兩個節點 a, b 所在的集合想要合併成一個集合
做法為找到兩集合的根節點
將其中一個集合的根節點連到另外一個的根節點
以下圖為例

union 函數
合併 2 所在的的集合 跟 7 所在的集合

則先找到 2 的根節點 =1, 7 的根節點 =6
將其中一個根節點的父節點設為另一個根節點
則 7 所在的集合所有元素的根節點都會變成 1
union 函數
這邊合併的函數名稱不使用
因為 union 為關鍵字 (撞名內建函數)
因此名稱改用 merge
初始化
一開始每個元素皆屬於屬於不同集合
因此會將節點指向自己,因為這時候每個元素都是根節點
完整程式碼
優化
在最差的情況下
合併後的集合的樹形有可能會變成一條鏈
\(\rightarrow\) find() 複雜度退化成 \(O(N)\)

以上圖為例,find(5) 需要跑完全部節點才能找到根節點
啟發式合併
Union by Rank
記錄每棵樹的大小,並在每次合併的時候,將小的集合合併到大的集合。
做法
宣告 sz 陣列,紀錄每個節點的為根的集合大小
在初始化的時候將每個集合大小 sz[i] 都設成 1
當遇到合併操作時,將兩個集合合併成一個時
把小的集合往大的集合合併
找到根節點,根節點儲存整個集合的資訊
合併時,把小的集合的資訊加給大的集合
分析
如果是原本的做法

假設有 \(n\) 個節點,合併 \(n - 1\) 次
每次合併都由大小為 \(i\) 的合併到大小為 \(1\) 的,樹就會長成最差的情況(鏈)
每次查詢會退化到 \(O(n)\)
分析
合併兩棵樹高不同的樹

兩個不同的集合合併,如果把樹高比較矮的連往比較高的,

合併後的樹高不會改變
而如果合併的兩個集合樹高相同,
或者高的往矮的合併,則合併後樹高會+1
每次把小的合併到大的方法,
稱之為啟發式合併
使用此方法的合併的樹,在最差情況下
為每次合併時,兩棵樹的樹高都相同
在樹高相同的情況下,會發現每次樹高要 + 1

所需節點數量會變 2 倍
因此 \(n\) 個節點時,使用啟發式合併樹高最高為 \(O(\log n)\)
優化 2
路徑壓縮
路徑壓縮
在每次 find() 的時候
把經過節點的父節點 全部設成根節點
呼叫 find(5) 會經過節點 5 4 3 2 1
將中間每個節點的父節點直接設為根節點
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →\(\rightarrow\)
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →使用啟發式合併+路徑壓縮
能使得單次操作複雜度降到 \(O(\alpha(N))\)
\(O(\alpha(N))\) 趨近於 \(O(1)\)
(\(\alpha( 2^{2^{10^{19729}}} ) = 5\))
因此並查集操作複雜度 幾乎是常數時間
完整程式碼
要特別注意合併時,如果兩個元素本來就在同一個集合
要直接回傳,不要重複加到 sz (15行)
紀錄集合資訊
如果題目為給定 \(n\) 個元素,每次操作為以下其中一種 :
查詢集合大小
會發現集合大小在做啟發式合併時,
就已經記錄過此資訊 sz[] 了
查詢元素 \(x\) 所在的集合大小只需要找到 \(x\) 的集合的根節點,
即為所在的集合的大小
如果題目需要求其他資訊,如集合內編號最小/大值等等,
則多為一個陣列 mn[]/mx[] 之類維護每個集合內的資訊
合併集合時,則把兩個集合內的資訊合併
相異集合的數量
要找總共有幾個集合,
可以找總共有幾個根節點即可
並查集在圖論上的意義
給一張 \(n\) 個節點的圖,一開始有 \(m\) 條邊,
接下來有 \(k\) 次操作,每次操作為新增一條邊,
每次操作完輸出最大的連通塊大小 ?
下圖為例,黑色為一開始的邊,

紅色為依序要加入的邊
當加完 1 號邊之後,最大連通塊大小為 5
當加完 2 號邊之後,最大連通塊大小為 5
當加完 3 號邊之後,最大連通塊大小為 6
連通塊意義
在同一個連通塊中,在並查集中代表在同一個集合。
因此我們可以用並查集維護整張圖誰跟誰連通。
在圖上邊 (x, y) ,相對於 merge(x, y) 操作
並查集應用
Almost-union-find
題序:一個有三種操作的並查集
可以發現操作 1、3 都是正常的並查集操作
只需要在 merge 的時候維護總和(sum)跟大小(sz)
而操作 2 比較不一樣,需要做到刪除的操作。
我們可以從兩種情況來看刪除
1. 移除的是葉節點
在這個情況下,我們只要將根節點記錄大小跟總和的變數把這個節點減掉即可。
2. 移除的不是葉節點
感覺很麻煩,我也不會
捨棄原本的節點
每次詢問,需要回傳集合內元素個數與元素編號總和
把元素 \(x\) 移除,其實只需把 \(x\) 儲存在集合內的資訊移除即可
移除後,原本的節點就不重要了。
加入到新的集合中
要將 \(x\) 加入新集合,可以先給 \(x\) 一個新的編號 \(newid\)
來代表數字 \(x\)
因此我們需要開一個陣列 id[] 維護每個元素當前代表的編號,
並初始化新編號的 sz[], num[]
換新編號 & 合併 x 與 y 的集合
反著做回來的題目
例題
題序:給一張 \(n\) 個點、\(m\) 條邊的圖,
要做 \(q\) 次操作,每次將一條邊拔掉
求每次拔掉後還有多少塊連通塊?
範圍: \(n, m, q\le 10^6\)
做法
每次刪除後看有幾個連通塊需要花 \(O(n + m)\) 的時間
而我們有 \(q\) 次詢問,很明顯不能這樣做
那這題要怎麼用並查集維護連通塊呢?
做法
如果將刪除變成合併,就跟原本 3-34 的題目類似了?
因此我們可以將操作反過來做
從後往前做,可以發現這樣子操作就從刪除變成合併了!
最小生成樹
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →「生成樹」。從一張圖取出一棵樹,包含圖上所有點。可能有許多種。
而最小生成樹是其中所有的生成樹中,權重總和最小的。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →Kruskal' algorithm
greedy method , 將所有邊照權重大小排序,從權重小的邊開始窮舉,依序窮舉到大,
當邊兩側的節點原本不連通就加邊,否則就捨棄這條邊
這個做法是對的,但為什麼是對的 🤔
證明
生成樹的一個性質:
對於兩個生成樹 \(T_1\) 與 \(T_2\) 和一條邊 \(e \in T_1 \backslash T_2\)
存在 \(e_2 \in T_2 \backslash T_1\) 使得 \((T_2\backslash \{e_2\})\cup \{e_1\}\) 依然是生成樹。
從 \(T_1\) 拿出一條邊加入 \(T_2\) 後,\(T_2\) 會形成一個環,此時移除環上任一邊即可讓 \(T_2\) 有 \(n-1\) 條邊連通,這個時候 \(T_2\) 也還會是一棵樹。
Kruskal' algorithm 的證明:
令Kruskal演算法找到的生成樹為 \(T\),而最小生成樹為 \(T^*\)
如果有多個最佳解,令 \(T^*\) 為與 \(T\) 交集最大的一個。
如果 \(T=T^*\) 就結束了,否則,令 \(e_i\) 是只出現在 \(T\) 的邊且編號最小
根據上面的性質,存在 \(e_j \in T^* \backslash T\) 使得 \(T^*\) 把 \(e_j\) 換出去再把 \(e_i\) 放進來仍是一棵生成樹。
假如 \(i < j\),那 \(e_i\) 的權重 \(\leq e_j\) 的權重。但由於\(T^*\)是最小生成樹,這樣做出來的 \(T\) 的權重會跟 \(T^*\) 一樣(或更小),但是與\(T\)的交集比 \(T^*\) 大,矛盾。
假如 \(i > j\),由於比 \(j\) 前面的邊都在 \(T\) 與 \(T^*\) 中,根據 Kruskal 演算法的特性,在遇到 \(e_j\) 時就會把 \(e_j\) 加入 \(T\) 中了,矛盾。
故得證 \(T=T^*\)
加入邊
使用並查集,一開始所有點都沒連任何邊
因此所有點都屬於自己的集合
當兩個點有連邊,代表他們屬於同一個集合
因此可以用並查集判斷,判斷是否已經為同一個集合
結構
使用 struct 儲存邊 (邊的兩個端點 u, v、權重 w)
多載 < 小於運算子,使用邊權重比較兩條邊的大小關係
程式碼
將邊照大小依序嘗試加入圖中,
如果邊的兩點未連通,則連通兩點
瓶頸生成樹
令 \(T_i\) 是這張圖的所有生成樹,會有樹 \(T^*\) 它的最大邊權值為所有 \(T_i\) 的最小
性質:
最小生成樹是瓶頸生成樹的充分不必要條件。
即最小生成樹一定是瓶頸生成樹,而瓶頸生成樹不一定是最小生成樹。
複雜度分析
依照權重排序所有邊 \(O(M\log M)\)
窮舉每條邊加入 \(O(M\cdot \alpha (N))\)
-> 總複雜度 \(O(M\log M)\)
Question Time and Practice
https://vjudge.net/contest/661401