---
type: slide
---
<style>
.reveal .slides {
text-align: left;
font-size:32px;
}
</style>
## Speical Graph & 0-1 BFS
Advanced Competitive Programming
2/16
----
- Functional graph
- Jellyfish graph
- Cactus graph
- 0-1 BFS
----
## Functional Graph
有向圖，每個節點出度恰好 1
----
Functional Graph 的特性
- 每個連通子圖都是由一個環 + 一些往環連向的邊所組成
- 每個點都有下一個點，因此也被稱為 successor graph
----
## Functional Graph 經典問題
----
## Functional Graph 走 k 步
給定一張 Functional Graph，$q$ 筆詢問，
每次求到從點 $x$ 走 $k$ 步的點是誰?
succ(2, 2) = 4
succ(3, 8) = 1
----
~~O(k)~~
$O(\log k)$?
----
## binary lifting method
如同求 LCA 的作法
對於每個點紀錄跳 $2^0$, $2^1$, $2^2$, $2^3$,... $2^k$ 步之後走到哪
如果要求走 $k$ 步之後的節點為何，只需把 $k$ 分解成二進位
走 11 $(1011_2)$ 步等價於走 8$(1000_2)$ 步 + 走 2$(10_2)$ 步 + 走 1$(1_2)$ 步
----
succ(2, 11) = succ(succ(succ(2, 8), 2), 1)
找出 2 走 11 步，先走 8 步，再走 2 步，再走 1 步
----
因此只需建出倍增表，
紀錄每個節點跳 $2^0$, $2^1$, $2^2$, $2^3$,... $2^k$ 步之後走到哪即可
$q$ 筆詢問即可在 $O(n\log n+q\log q)$ 的時間內做到
----
[DDJ a419: k-th node](http://203.64.191.163/ShowProblem?problemid=a419)
給一張 Functional Graph，求每個節點走 $k$ 步分別會到哪個節點 ?
$1\le n\le 10^5$
$1\le k\le 10^{18}$
----
建倍增表?
----
其實不用那麼麻煩，
只需一個快速冪即可
對於每個節點都要求出走 $k$ 步之後會到哪。
----
每次把節點跳當前的兩倍距離，
再看 $k$ 的二進位哪些 bit 為 1，在 $2^{bit}$ 的時候跳即可
----
時間複雜度 : $O(n\log k)$
空間複雜度 : $O(n)$
----
## Functional Graph 找環
給一張 Functional ，照順序輸出環上的點的編號
----
直覺的作法，DFS 找環
由於 Functional 上的每個點不是在環上，
就是在往環的路上。
可以從隨便一個點出發，DFS 把走過的點都記錄起來，
其中一個點走過第二次即為環上的點
時間、空間複雜度 : $O(N)$
----
## Floyd's Algorithm
龜兔賽跑演算法
只需要兩個變數即可找到環
----
兩個變數 a, b 分別代表烏龜和兔子，
從起點 x 同時出發，
烏龜每次走一步，兔子每次走兩步。
```cpp=
int a = x, b = x;
while(a != b){
a = next[a];
b = next[next[b]];
}
```
兩個一直跳到同一個節點為止
----
環的大小則固定一個點後，
另一個點跑一圈回到原點即可計算
---
## Jellyfish graph
水母圖，圖如其名
由恰好一個簡單環 + 一些樹組成的連通圖
 
無向圖的 functional graph
----
常見的題型為樹上 DP 題變成水母圖上去做
水母圖上最小點覆蓋，最大獨立集等等
----
### [ICPC 2020 台北站 F. Cable Protection](https://drive.google.com/file/d/1v6vk-VEtyNNDbTPOlc1JE_m9VllTHwi0/view)
給一張水母圖，求最小點覆蓋。
----
把環上延伸出去的樹的 DP值/累積答案先算完，
再把剩下的 case 在環上合併
----
其中一個好的處理順序是從所有葉節點開始往環的方向 DP 回去
可以用 BFS 每次把 degree = 1 的點拔掉，
最後只會剩下環上的點而已
---
## Cactus graph
仙人掌圖，圖如其名，一球一球的
 
----
## 仙人掌圖的定義
仙人掌圖有很多可能的定義，根據題目給定
- 每條邊在恰好一個簡單環上
- 每條邊在最多一個簡單環上
 
----
## 經典問題 --- 判斷一張圖是否為仙人掌圖
判斷每條邊是否在恰好一個環上
----
### 作法
DFS，用 stack 維護當前遍歷的節點，
走到重複的節點就回退，把這個環上的點都記錄+1。
( 環的起點不加，因為一個點可以在多個環上 )
如果有節點被記錄超過 1 則此圖不是仙人掌圖。
<font color="#303030"><small>或者砸 SCC/BCC 模版在判斷每個環是否為簡單環</small></font>
----
## ~~出題法則~~
~~如果想把序列上的題目加難~~
$\to$ ~~就把他出在樹上~~
~~如果想把樹上的題目加難~~
$\to$ ~~就把他改成仙人掌圖~~
---
## 0-1 BFS
當邊權只有 1 的最短路徑時，會使用 BFS 來實作
複雜度 $O(|E|)$
但是當邊權只有 0 或 1 的時候，可以使用 0-1 BFS
用一樣 |O(|E|)| 的複雜度
來降低 dijkstra 所需要 priority_queue 的 $O(\log E)$ 複雜度
----
## BFS vs 0-1 BFS
BFS 時，我們的 queue 中的元素到原點的距離最多相差 1
queue 中的元素可能如下，最前面那段為距離 d, 中間某個開始之後都是距離 d+1
```
queue = [a,...,b, c,...,d]
dis d d d d d+1 d+1 d+1
```
----
而 0-1 BFS 多了邊權為 0 的邊，
那就和原本 queue 取出的元素距離相同
我們是從頭拿出來的，那就塞回去頭的位置
但 queue 做不到這件事情，改用 deque 維護
----
```cpp=
deque<int> que;
que.push(s);
while(!que.empty()){
int u = que.front(); que.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int [v, w] : edge[u]){
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(w == 1) que.push_back(v);
else que.push_front(v);
}
}
}
```
----
### CodeChef - Chef and Reversing
給一張有向無權圖，求最少要翻轉幾條邊能從節點 1 走到節點 n
上圖答案為 2
----
對於一條有向邊 $(u, v)$ 分別建兩條邊
$(u, v, 0)$，走原本給的路
$(v, u, 1)$，翻轉該邊
然後跑最短路，最短路的成本即為翻轉的次數
----
### Atcoder - abc246E. Bishop 2
給一個 $n\times n$ 的西洋棋盤棋盤
有一些格子是障礙物，給你一隻主教在位置 $(s_x, s_y)$
主教每次可以往對角線方向移動任意步 (不能穿越障礙物)
求移動到位置 $(e_x, e_y)$ 要幾步
$1\le n\le 1500$
----
```
....#
...#.
.....
.#...
#....
```
$s = (1, 3)$
$e = (3, 5)$
$(1, 3)\to (2, 2)\to (4,4)\to (3, 5)$
----
如果每次都暴力把四個方向可以走的位置都更新一遍，
那複雜度很明顯是爛的 $O(n^3)$
想一下如何套 0-1 BFS 到這題上?
----
分成兩種 case
1. 往其中一個方向走一單位，花費 1
2. 延續剛剛走的繼續走，花費 0
```
......
.1.1..
..S...
.1.1..
......
......
```
```
0...0.
.1.1..
..S...
.1.1..
0...0.
.....0
```
----
即可轉變為 0-1 BFS !
實作上的細節要分成四個方向記錄是否可以走
----
## Dial's algorithm
而如果所有的邊權重都 $\le k$，
也可以開 $k+1$ 個 queue 來分別維護從當前距離 $v$ 開始一直到距離 $v+k$ 的更新點
每當距離 $v$ 的 queue 空了就位移到下一個 queue，然後環狀的維護這些 queue
複雜度最差為 $O(nk)$
Google Drive
Gist
Clipboard
Sign in with Wallet
