---
# System prepended metadata
title: Advanced Graph Algorithm
tags: [2023-summer]
---
---
type: slide
---
# Advanced Graph Algorithm
----
- Biconnected Component
- Strongly Connected Components
- 2-SAT
- Maximum Clique
- Minimum Mean Cycle
---
## Biconnected Component
### 點雙連通分量
----
無向圖上，不會產生割點的連通分量
稱為點雙連通分量
----
## 名詞定義
### Articulation (關節點)：
讓圖保持連通不可或缺的點
維持多個不同的連通分量，如果拔掉那個點，
則圖會分成多個不同的連通塊
以右圖為例，拔掉點 2 則圖會不連通
### Bridge (橋)：
讓圖維持連通的邊，
如果拔掉那條邊，則圖會不連通
以右圖為例，拔掉連接 1 5 的邊則圖會不連通
----
## Tarjan algorithm
----
## 回傳值
二維vector，分別為連通分量跟橋
vector size = 2 的為橋
vector size \> 2 的為點雙連通分量
``{
{0,2,4,6,7},
{2,3,5},
{1,5}
}``
----
## 求關節點
可以發現如果一個點是關節點，則他會存在聯繫多個連通分量，
因此就直接判斷每個點出現次數，如果出現在多於一個連通分量，
則此點為關節點
----
[模板](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$ 的路徑
則為強連通分量
----
## 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 |
- `+1(1) +2(2)`
add_edge(1, 7)
add_edge(2, 6)
- `-1(6) +3(3)`
add_edge(6, 8)
add_edge(3, 1)
- `+4(4) -2(7)`
add_edge(4, 2)
add_edge(7, 9)
----
## 求解
建完圖之後跑 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)$ 即可做
----
### 另一個例題
### [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 即可求解
---
## 最大獨立集
一張圖上，最多能選幾個點，使得選的點彼此都不沒有連邊
以上圖為例，選 3、5、7、8 四個點為一組解
----
## 最大團
一張圖上，最多可以選幾個點，使選的彼此之間都有連邊
以上圖為例，選 1、2、5、6 四個點為一組解
----
最大獨立集本身沒有好的做法，只能窮舉 subset 複雜度 $O(2^{N}M)$
而最大團目前最佳複雜度為 $O(1.1888^n)$
因此最大獨立集通常會轉換為用補圖做最大團
----
## 作法
獨立集 與 團 的概念完全相反
最大獨立集去建反圖之後，求最大團即可得到答案
$\to$
----
[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/MaximumClique.cpp)
- init(n);
- 初始化圖
- addEdge(u, v);
- 建一條雙向邊 (u, v)
- solve();
- 回傳值為最大團的點數量
$O(1.1888^n)$，約可以做到 n 為 100 多
----
### [2013 ICPC Chia-Yi --- A Generalized N-Queens Problem](https://vjudge.net/problem/UVALive-6696)
給一個 $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 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 通過
---
[Homework](https://vjudge.net/contest/570924)