<style> .reveal .slides { text-align: left; font-size:30px } </style> # Advanced Graph Algorithm ---- - Biconnected Component - Strongly Connected Components - 2-SAT - Maximum Clique - Minimum Mean Cycle - Dominator Tree ---- ## 講義勘誤 7-1. 支配樹能求解對象為 "有向圖"，而非 "DAG"。 --- ## Biconnected Component ### 點雙連通分量 ---- 無向圖上，不會產生割點的連通分量 稱為點雙連通分量 <div style="position: absolute; right: 0%; top:30%;">  </div> ---- ## 名詞定義 ### Articulation (關節點)： 讓圖保持連通不可或缺的點 維持多個不同的連通分量，如果拔掉那個點， 則圖會分成多個不同的連通塊 以右圖為例，拔掉點 2 則圖會不連通 ### Bridge (橋)： 讓圖維持連通的邊， 如果拔掉那條邊，則圖會不連通 以右圖為例，拔掉連接 1 5 的邊則圖會不連通 <div style="position: absolute; right: -10%; top:30%;">  </div> ---- ## Tarjan algorithm <div style="position: absolute; right: 70%; top:80%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 回傳值 二維vector，分別為連通分量跟橋 vector size = 2 的為橋 vector size \> 2 的為點雙連通分量 ``{ {0,2,4,6,7}, {2,3,5}, {1,5} }``  ---- ## 求關節點 可以發現如果一個點是關節點，則他會存在聯繫多個連通分量， 因此就直接判斷每個點出現次數，如果出現在 > 1 個連通分量中， 則此點為關節點  ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/bcc_vertex.cpp) ```cpp= #define PB push_back #define REP(i, n) for(int i = 0; i < n; i++) ``` - init(n); - 初始化圖 - addEdge(u, v); - 建一條無向邊 (u, v) - solve(); - 跑 BCC - 回傳二維 vector，每個一維 vector 是一個連通分量 ---- ### 例題 --- [Critical Structures (2019 ICPC Taipei Site)](https://codeforces.com/gym/102835) 給一張無向圖，找出 - 關節點的數量 - 橋的數量 - 有幾個點雙連通分量 - 最多邊的連通分量有幾條邊 $1\le n\le 1000$ $1\le m\le 10^6$ ---- ### 關節點的數量 & 橋的數量 這兩個用模板前述作法即可求出 ---- ### 點雙連通數量 即為回傳的 vector.size() 即為點雙連通數量 ---- ### 最多邊的連通分量有幾條邊 遍歷所有連通分量， 看每個連通分量內的邊有幾個 ---- 因此，只需要會套模板即可通過這題 [PI 賽中只有 14/101 隊通過](https://raw.githubusercontent.com/jakao0907/CompetitiveProgrammingCodebook/master/scoreboard/icpc2020.png) --- ## strongly connected components (SCC) ### 強連通分量 在有向圖裡的任兩點 $u、v$， 皆存在至少一條 $u$ 到 $v$ 的路徑以及 $v$ 到 $u$ 的路徑 則為強連通分量 <div style="position: absolute; right: -5%; top:30%;">  </div> ---- ## kosaraju's algorithm 把一張有向圖，拆成很多個強連通分量  $\to$  ---- ## 縮點 縮點之後原本的環就都會不見，變成有向無環圖(DAG)  $\quad\to\quad$  ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/kosaraju.cpp) ```cpp= #define PB push_back #define FZ(x) memset(x, 0, sizeof(x)) //fill zero ``` - init(n); - 初始化圖 - addEdge(u, v); - 建一條有向邊 (u, v) - solve(); - 跑 SCC 結果存在 bln 陣列中，代表每個點所屬於哪個強連通分量 nScc 代表有幾個強連通分量 ----  $\quad\to\quad$  複雜度 $O(n+m)$ ---- ### [CSES --- Planets and Kingdoms](https://cses.fi/problemset/task/1683) n 個城市，m 條單向道路， 如果兩個城市彼此可走到對方，則屬於同一個王國， 問總共有幾個王國? 並且對於每個王國，輸出任意一個城市。 ---- 王國數量即為 nScc， 對於每一個王國，只需要找每個 bln 裡面的其中一個節點即可 ---- ## SCC + DP 由於 SCC 經過縮點之後會變成一張 DAG 因此很多一般有向圖上的問題，轉成 DAG 後即可在 DAG 上 DP ---- ## [CSES --- Coin Collector](https://cses.fi/problemset/task/1686) 給定一張有向圖，每個節點上有 $k_i$ 個硬幣， 如果選擇一條路徑 (可以經過重複節點) 走，最多可以拿到多少硬幣 ? ---- 會發現這題跟上學期 DP on DAG 的作業&期中考長很像 [Mango Cake](https://vjudge.net/contest/544447#problem/C) 只是一題是在 DAG 上，一題在一般有向圖上 ---- 而我們只需要把有向圖縮點後轉成 DAG， 把同一個環上的點權重總和加起來  $\quad\to\quad$  即為 DP on DAG ---- ### 實作 把同一個強連通分量的點合併成同一個點， 可以直接用 bln 當成新圖的編號建圖 用 bln 建出的新圖跑 DP on DAG ```cpp= // 把原本的點權合併到 bln 的點上 for(int i = 0; i < n; i++) sum[scc.bln[i]] += w[i]; // 用 bln 建新圖 for(int i = 0; i < m; i++){ auto [u, v] = edge[i]; if(scc.bln[u] != scc.bln[v]) new_edge[scc.bln[u]].push_back(scc.bln[v]); } ``` --- ## 2-SAT ### 2-satisfiability problem 有 $N$ 個 boolean 變數 $a_1 \sim a_N$ 接著有 $M$ 條需要滿足的式子 ($a_i$ is `true/false` or $a_j$ is `ture/false`) 問有沒有可能決定 $N$ 個變數分別為 `true/false` 的情況下， 滿足 $M$ 條式子 $(\neg a_1\ or\ a_2)\ and\ (a_2\ or\ a_3)\ and\ (\neg a_3\ or\ \neg a_4)$ ---- $(\neg a_1\ or\ a_2)\ and\ (a_2\ or\ a_3)\ and\ (\neg a_3\ or\ \neg a_1)$ - $\neg a_1\ or\ a_2$ (滿足 $a_1$為false 或者 $a_2$為true) - $a_2\ or\ a_3$ (滿足 $a_2$為true 或者 $a_3$為true) - $\neg a_3\ or\ \neg a_1$ (滿足 $a_3$為false 或者 $a_1$為false) 一個合法解為 $a_1 = true, a_2 = true, a_3 = false$ ---- ## 舉個例子 [Giant Pizza](https://cses.fi/problemset/task/1684) 有 $N$ 個要訂披薩，披薩有 $M$ 種配料 每個人有 2 個願望，願望可能為 (希望/不希望披薩出現配料 $a_i$ ) 問每個配料加或不加，是否能滿足每個人至少一種願望 #### sample input ```txt 3 5 + 1 + 2 - 1 + 3 + 4 - 2 ``` #### sample output ```txt - + + + - ``` (配料1要加 or 配料2要加) and (配料1不要加 or 配料3要加) and (配料4要加 or 配料2不要加) ---- 會發現如果要暴力找到一組合法解最差情況要花 O($2^N\cdot M$) $N$個變數窮舉 true/false, 再去檢查是否滿足 $M$ 個式子 但題目的 $N, M$ 為 $10^5$ $\to$ TLE ---- ## 轉成圖論 scc 作法 2-SAT 問題可以轉換成 SCC 去求解 只需把每個狀態轉成節點/邊即可 ---- 每個變數有 True, False 兩種可能的狀態 也就是 $a_i$ ($i$ = True) 或者 $\neg a_i$ ($i$ = False) 以剛剛那題就是要加第 $i$ 種配料或者不加第 $i$ 種配料 ---- 把每個變數的兩種狀態 True/False 轉成圖論的節點編號 | 狀態\變數 | 1 | 2 | 3 | | -- | --- | --- | --- | | True | 1 | 2 | 3 | | False | 4 | 5 | 6 | 節點 1 為變數 1 的 True 狀態 節點 2 為變數 2 的 True 狀態 節點 3 為變數 3 的 True 狀態 節點 4 為變數 1 的 False 狀態 節點 5 為變數 2 的 False 狀態 節點 6 為變數 3 的 False 狀態 ---- 對於一個限制 (x or y) 則加兩條邊 - x $\to$ $\neg$y - y $\to$ $\neg$x ---- ## 建邊 ```txt 3 5 + 1 + 2 - 1 + 3 + 4 - 2 ``` | 狀態\變數 | 1 | 2 | 3 | 4 | 5 | | -- | --- | --- | --- | --- | --- | | True | 1 | 2 | 3 | 4 | 5 | | False | 6 | 7 | 8 | 9 | 10 | <div style="position: absolute; right: 70%; top:120%;"> - `+1(1) +2(2)` add_edge(1, 7) add_edge(2, 6) </div> <div style="position: absolute; right: 40%; top:120%;"> - `-1(6) +3(3)` add_edge(6, 8) add_edge(3, 1) </div> <div style="position: absolute; right: 10%; top:120%;"> - `+4(4) -2(7)` add_edge(4, 2) add_edge(7, 9) </div> ---- ## 求解 建完圖之後跑 scc，對於每個變數 判斷每個變數兩種狀態(true/false) 的 bln 如果 true 狀態的 bln 比較小則為 true - scc.bln[i] < scc.bln[not i] 否則 false 狀態的 bln 比較小則為 false - scc.bln[not i] < scc.bln[i] 如果 true 狀態的 bln 和 false 狀態的 bln 相等，則無法滿足所有條件 - scc.bln[i] == scc.bln[not i] 都符合則找到一組合法解 ---- ## 複雜度 N 個變數分別兩種狀態 2N 建 2M 條邊 再跑SCC 複雜度 $O(N+M$) 通常題目如果只有兩種狀態，要或不要，塗黑色或白色...等 並且求一組合法解就有可能是 2-SAT 想想看能不能把條件轉成 $(\neg a_1\ or\ a_2)\ and\ (a_2\ or\ a_3)\ and\ (\neg a_3\ or\ \neg a_1)$ 即可做 ---- ### 另一個例題 ### [2022 NCPC Final --- G. Rounding](https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=65416) 給一個 $N\times N$ 的數字矩陣 $a$，每個 row/column 各自**最多**兩個浮點數，其他都為整數 $\left( \begin{array}{ccc} 6.3 & 7 & 4.6\\ 4.7 & 2 & 2 \\ 5 & 4.5 & 3.4 \\ \end{array} \right)$ 要把每個小數都選擇進位或捨去，變成矩陣 $b$ ---- 使得最後滿足 $\forall i =\{1,2,3,...n\}, \sum\limits_{j=1}^{n} b_{ij} = \lfloor \sum\limits_{j=1}^{n} a_{ij}\rfloor$ or $\sum\limits_{j=1}^{n} b_{ij} = \lceil \sum\limits_{j=1}^{n} a_{ij}\rceil$ $\forall j =\{1,2,3,...n\}, \sum\limits_{i=1}^{n} b_{ij} = \lfloor \sum\limits_{i=1}^{n} a_{ij}\rfloor$ or $\sum\limits_{i=1}^{n} b_{ij} = \lceil \sum\limits_{i=1}^{n} a_{ij}\rceil$ 每個 row/column 的總和等於原始數值總和的上或下取整 ---- $\left( \begin{array}{ccc} 6.3 & 7 & 4.6\\ 4.7 & 2 & 2 \\ 5 & 4.5 & 3.4 \\ \end{array} \right)$ $\to$ $\left( \begin{array}{ccc} 7 & 7 & 4\\ 4 & 2 & 2 \\ 5 & 4 & 4 \\ \end{array} \right)$ 每個 row/column 的總和等於原始數值總和的上取整或下取整 ---- ## 轉換問題 變成原始矩陣的上取整或下取整，可以分成以下幾種 case: - 兩個小點數加起來 $> 1$，則兩個浮點數轉換至少一個進位 - 兩個小點數加起來 $= 1$，則兩個浮點數轉換恰好一個進位 - 兩個小點數加起來 $< 1$，則兩個浮點數轉換至多一個進位 $\left( \begin{array}{ccc} 4.2 & 5.6 \\ 1.1 & 3.9 \end{array} \right)$ 4.2 + 5.6 = 9.8 $\to$ 9 or 10 1.1 + 3.9 - 5 $\to 5$ 5.6 + 3.9 = 9.5 $\to$ 9 or 10 ---- 每個小數是否進位轉換為狀態 $a_i$ = True 代表進位 $a_i$ = False 代表不進位 ---- 兩個浮點數 $i, j$ 轉換至少一個進位 - $a_i =$ True $\vee$ $a_j =$ True ---- 兩個浮點數 $i, j$ 轉換恰好一個進位 - (a_i =$ True $\vee$ $a_j =$ True) $\land\ (a_i =$ False $\vee$ $a_j =$ False) ---- 兩個浮點數 $i, j$ 轉換至少一個不要進位 - $a_i =$ False $\vee$ $a_j =$ False ---- 根據每個 row/column 的情況轉換 - 兩個小點數加起來 $> 1$，則兩個浮點數轉換至少一個進位 - 兩個小點數加起來 $= 1$，則兩個浮點數轉換恰好一個進位 - 兩個小點數加起來 $< 1$，則兩個浮點數轉換至多一個進位 建圖跑 SCC 即可求解 ---- 對於條件 (X or Y) 如果覺得建邊 ($X\to \neg Y$) ($Y\to \neg X$) 很難記的話，可以參考這個記法: 不選 X，就要選Y 不選 Y，就要選X 或許會比較好記一點 不過還是建議把建邊方法放模板以防太久沒用忘記 --- ## 最大獨立集 一張圖上，最多能選幾個點，使得選的點彼此都不沒有連邊  以上圖為例，選 3、5、7、8 四個點為一組解 ---- ## 最大團 一張圖上，最多可以選幾個點，使選的彼此之間都有連邊  以上圖為例，選 1、2、5、6 四個點為一組解 ---- 最大獨立集本身沒有好的做法，只能窮舉 subset 複雜度 $O(2^{N}M)$ 而最大團目前最佳複雜度為 $O(1.1888^n)$ 因此最大獨立集通常會轉換為用補圖做最大團 ---- ## 作法 獨立集 與 團 的概念完全相反 最大獨立集去建反圖之後，求最大團即可得到答案 <div style="position: absolute; right: 70vh; top: 38vh"> $\to$ </div> <div style="position: absolute; right: 70%;">  </div> <div style="position: absolute; right: 25%;">  </div> ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/MaximumClique.cpp) - init(n); - 初始化圖 - addEdge(u, v); - 建一條雙向邊 (u, v) - solve(); - 回傳值為最大團的點數量 $O(1.1888^n)$，約可以做到 n 為 100 多 通常題目最大會出到 80-100 左右 ---- ### [2013 ICPC Chia-Yi --- A Generalized N-Queens Problem](https://vjudge.net/contest/633971#problem/J) 給一個 $N\times N$ $(N\le 10)$ 的網格圖，有些格子已經放障礙物了。 圖上最多可以放幾個皇后，才能不會攻擊到對方。  上圖為例可以放三個 ---- 會發現 N 特別小，整個圖的大小只有 100 最大獨立集? ---- 如果兩個皇后位於同一 row/column/diagonal ， 並且中間沒有障礙物的話不能同時存在， 我們可以把每個非障礙物的位置當成一個節點，互相可以攻擊到對方的位置連邊跑最大獨立集，即為答案 ---- ## 極大團 對於一張圖，選任意的點子集，如果不能在多選一個點使得選的點子集為更大的團  以上圖為例 {1, 4} 為一個極大團 {2, 3} 並非極大團，因為可以再多加點 6 變成更大的團 {1, 2, 3}, {2, 3, 6} {3, 5, 6} 也為極大團 ---- 程式碼中會不斷窮舉極大團 每次跑到第 20 行時，cans(bitset) 中值為 1 的節點代表在當前窮舉的極大團裡 ```cpp= [|6-10|11-12|32-44|20|] #define N 80 struct MaxClique{ // 0-base typedef bitset<N> Int; Int lnk[N] , v[N]; int n; void init(int _n){ n = _n; for(int i = 0 ; i < n ; i ++){ lnk[i].reset(); v[i].reset(); } } void addEdge(int a , int b) { v[a][b] = v[b][a] = 1; } int ans , stk[N], id[N] , di[N] , deg[N]; Int cans; void dfs(int elem_num, Int candi, Int ex){ if(candi.none()&&ex.none()){ cans.reset(); for(int i = 0 ; i < elem_num ; i ++) cans[id[stk[i]]] = 1; ans = elem_num; // cans is a maximal clique return; } int pivot = (candi|ex)._Find_first(); Int smaller_candi = candi & (~lnk[pivot]); while(smaller_candi.count()){ int nxt = smaller_candi._Find_first(); candi[nxt] = smaller_candi[nxt] = 0; ex[nxt] = 1; stk[elem_num] = nxt; dfs(elem_num+1,candi&lnk[nxt],ex&lnk[nxt]); } } int solve(){ for(int i = 0 ; i < n ; i ++){ id[i] = i; deg[i] = v[i].count(); } sort(id , id + n , [&](int id1, int id2){ return deg[id1] > deg[id2]; }); for(int i = 0 ; i < n ; i ++) di[id[i]] = i; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++) if(v[i][j]) lnk[di[i]][di[j]] = 1; ans = 1; cans.reset(); cans[0] = 1; dfs(0, Int(string(n,'1')), 0); return ans; } }solver; ``` --- ## Minimum Mean Cycle 給定一張有向圖，邊上有權重，要找到一個環其平均權重最小。  例圖中最小平均環為 2->3->4->2 平均為 $\frac{5}{3}$ ---- ### 2018 ICPC Taipei --- J. Mean Weight of a Critical Cycle 裸題， 給定一張有向圖，求出最小平均環，用最簡分數表示。 ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/MinMeanCycle.cpp) - init(n); - 初始化圖 - addEdge(u, v, w); - 建一條單向邊 (u, v) 權重為 w - solve(); - 回傳值為最小平均權重 (小數) 複雜度 $O(VE)$ ---- [賽中記分板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/scoreboard/icpc2018.jpg) 18/116 通過 --- ## Dominator Tree 基本定義: 給一張有向圖，圖上有一個起點 $S$ 可以走到所有點。 定義 "支配" 為從起點 $S$ 出發，所有能走到節點 $x$ 的路徑的最後一個必經點。  以節點 6 來說，最後一個必經點為 5 以節點 4 來說，最後一個必經點為 0 以節點 3 來說，最後一個必經點為 2 ----  以節點 6 來說，支配點為 5 以節點 4 來說，支配點為 0 以節點 3 來說，支配點為 2 除了起點 $S$ 以外，其他點都有支配點。 ---- [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/DominatorTree.cpp) 用法 1. init(n, s); // 節點數量，起點編號 1-base 2. addEdge(u, v); // 建邊 3. build(); // 建立支配樹 最後 $idom[i]$ 為點 $i$ 的支配點 複雜度 $O(n+m)$ ---- ## 經典題 給一張 DAG，求從 1 號節點出發，每個節點能支配的點的個數  2 號節點能支配的點為 1 4 號節點能支配的點為 1, 2, 3 8 號節點能支配的點為 1, 2, 3 9 號節點能支配的點為 1, 2, 3, 4, 7 ---- 把每個點的支配點當成父節點，形成的圖為一棵樹。 所有要求的問題即可轉為樹上問題。  ---- 每個節點能支配的點的個數轉成樹上問題， 即為從當前點到根節點的距離總和。 ---- 題單: https://vjudge.net/contest/633971 好用小工具: https://csacademy.com/app/graph_editor/