<style> .reveal .slides { text-align: left; font-size:30px; } </style> # graph (advanced) ---- - System of Difference Constraints - SCC/BCC - 2-SAT --- ## System of Difference Constraints 差分約束系統 ---- 是求解關於一組不等式之方法。 $n$ 個變數和 $m$ 個約束條件組成 其中每個約束條件形如 ${ x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}$ 則稱其為差分約束系統。 ---- ## 例子 ${x_{1}-x_{2}\leq 5}$ ${x_{1}-x_{3}\leq 1}$ $\to x_{1}=0, x_{2}=-5, x_{3}=-1$ ${x_{1}-x_{2}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$ $\to$ 無解 <div style="position: absolute; right: 10%; top:0%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 作法 轉成圖論問題 對於所有 $x_{j}-x_{i}\leq k$ 連接一條邊 $(i, j)$，權重為 $k$ 最後再設置一個起點 $s$，連向所有邊邊權為 $0$ 從起點 $s$，跑 SPFA ，若出現負環則代表這組不等式無解 ---- ## 建圖 ${x_{1}-x_{2}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$  ---- ## 結果 跑完 SPFA 如果發現有負環，則此組不等式無解 否則所有點到起點的距離為其中一組解 --- ## strongly connected components (SCC) ### 強連通分量 在有向圖裡的任兩點 $u、v$， 皆存在至少一條 $u$ 到 $v$ 的路徑以及 $v$ 到 $u$ 的路徑 則為強連通分量 <div style="position: absolute; right: -10%; top:30%;">  </div> ---- ## kosaraju's algorithm 把一張有向圖，拆成很多個強連通分量 <div style="position: absolute; right: 70%; top:80%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 縮點 縮點之後原本的環就都會不見，變成有向無環圖(DAG) <div style="position: absolute; right: 70%; top:80%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 例題 [Planets and Kingdoms](https://cses.fi/problemset/task/1683/) ### 題意 有 $N$ 個星球，如果兩個星球 $i$ 和 $j$ 彼此都有一條路到達彼此，則他們屬於同一個王國。 幫每個國家都標記一個編號，如果屬於同一個王國則編上同一個編號 ### 作法 對於兩個星期 $i,\ j$ 如果有路可以到彼此則為強連通分量 首先先把圖分成很多個強連通分量，接者看每個星球所屬的 bln 為多少 ---- ```cpp [|6-10|11-13|23-35|4|] #define FZ(x) memset(x, 0, sizeof(x)) #define PB push_back struct Scc{ int n, nScc, vst[MXN], bln[MXN]; // 最後每個點所屬的連通分量存在bln陣列 vector<int> E[MXN], rE[MXN], vec; void init(int _n){ //先初始化點的數量 n = _n; for (int i=0; i<MXN; i++) E[i].clear(), rE[i].clear(); } void addEdge(int u, int v){ // 加有向邊 E[u].PB(v); rE[v].PB(u); } void DFS(int u){ vst[u]=1; for (auto v : E[u]) if (!vst[v]) DFS(v); vec.PB(u); } void rDFS(int u){ vst[u] = 1; bln[u] = nScc; for (auto v : rE[u]) if (!vst[v]) rDFS(v); } void solve(){ // 跑 kosaraju nScc = 0; vec.clear(); FZ(vst); for (int i=0; i<n; i++) if (!vst[i]) DFS(i); reverse(vec.begin(),vec.end()); FZ(vst); for (auto v : vec) if (!vst[v]){ rDFS(v); nScc++; } } }; ``` ---- ## Biconnected Component (BCC) ### 點雙連通分量 無向圖上，不會產生割點的連通分量 稱為點雙連通分量 <div style="position: absolute; right: -10%; 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，分別為連通分量跟橋 ``{ {0,2,4,6,7}, {2,3,5}, {1,5} }``  ---- ## 求關節點 可以發現如果一個點是關節點，則他會存在聯繫多個連通分量， 因此就直接判斷每個點出現次數，如果出現在多於一個連通分量， 連接著多個連通分量，則此點為關節點  ---- ## 例題 https://zerojudge.tw/ShowProblem?problemid=c111 找幾個關節點 ---- ```cpp [|5-8|9-10|31-42|] struct BccVertex { int n,nScc,step,dfn[MXN],low[MXN]; vector<int> E[MXN],sccv[MXN]; int top,stk[MXN]; void init(int _n) { //初始化點的數量 n = _n; nScc = step = 0; for (int i=0; i<n; i++) E[i].clear(); } void addEdge(int u, int v) // 加無向邊 { E[u].PB(v); E[v].PB(u); } void DFS(int u, int f) { dfn[u] = low[u] = step++; stk[top++] = u; for (auto v:E[u]) { if (v == f) continue; if (dfn[v] == -1) { DFS(v,u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { int z; sccv[nScc].clear(); do { z = stk[--top]; sccv[nScc].PB(z); } while (z != v); sccv[nScc++].PB(u); } }else low[u] = min(low[u],dfn[v]); } } vector<vector<int>> solve() { // 跑 Tarjan vector<vector<int>> res; for (int i=0; i<n; i++) dfn[i] = low[i] = -1; for (int i=0; i<n; i++) if (dfn[i] == -1) { top = 0; DFS(i,i); } REP(i,nScc) res.PB(sccv[i]); return res; } }graph; ``` ---- SCC、BCC 非常重要 台灣站很常出 一個圖論題目加難的方法就是把題目變成需要用到這兩個 遇到有環可能會很難的題目，記得想想看能不能用SCC/BCC簡化他 --- ## 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 個願望，願望可能為 (希望/不希望披薩出現配料) 問每個配料加或不加，是否能滿足每個人至少一種願望 #### 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 作法 把每個變數分別轉成兩種狀態 true/false 並且把這兩種狀態編號起來 | 兩種狀態\N個變數 | 1 | 2 | 3 | | -- | --- | --- | --- | | True | 1 | 2 | 3 | | False | 4 | 5 | 6 | 把每種狀態分別當成圖論上的節點 對於一個限制 (x or y) 則加兩條邊 - x $\to$ $\neg$y - y $\to$ $\neg$x ---- ## 建邊 ```txt 3 5 + 1 + 2 - 1 + 3 + 4 - 2 ``` | 兩種狀態\N個變數 | 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 比較小則為 ture 否則false狀態的 bln 比較小則為 false 每個變數得到狀態後去驗證 $M$ 個條件， 如果其中一個條件不符合則代表無法滿足所有條件 都符合則找到一組合法解 ---- ## 複雜度 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)$ 即可做 --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/498988) 提交期限到下星期三 6/15 23:59 截止