---
type: slide
---

<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

---

## 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}
}``

----

## 求關節點

可以發現如果一個點是關節點，則他會存在聯繫多個連通分量，
因此就直接判斷每個點出現次數，如果出現在多於一個連通分量，
則此點為關節點


----

[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/graph/bcc_vertex.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)

#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

// 把原本的點權合併到 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

3 5
+ 1 + 2
- 1 + 3
+ 4 - 2

#### sample output

- + + + -

(配料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

----

## 建邊

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 比較小則為 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)$

因此最大獨立集通常會轉換為用補圖做最大團

----

## 作法

獨立集 與 團 的概念完全相反

最大獨立集去建反圖之後，求最大團即可得到答案

<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 多

----

### [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 的節點代表在當前窮舉的極大團裡

#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 通過

---

[Homework](https://vjudge.net/contest/570924)