---
# System prepended metadata

title: Functional Graph & 01 BFS
tags: [2024-winter]

---

---

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

![image](https://hackmd.io/_uploads/SJOS55k5a.png)

----

Functional Graph 的特性

- 每個連通子圖都是由一個環 + 一些往環連向的邊所組成
- 每個點都有下一個點，因此也被稱為 successor graph

----

## Functional Graph 經典問題

----

## Functional Graph 走 k 步

給定一張 Functional Graph，$q$ 筆詢問，
每次求到從點 $x$ 走 $k$ 步的點是誰?

![image](https://hackmd.io/_uploads/SJQI9yl5p.png)

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)$ 步 


----

![image](https://hackmd.io/_uploads/SJQI9yl5p.png)

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

水母圖，圖如其名
由恰好一個簡單環 + 一些樹組成的連通圖

![image](https://hackmd.io/_uploads/B1qzFVg96.png =x300 ) ![9e8b425e-c0b6-4e95-9837-77fba039d0da](https://hackmd.io/_uploads/HyRxq4x9T.jpg =x300)

無向圖的 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

仙人掌圖，圖如其名，一球一球的

![image](https://hackmd.io/_uploads/r1md5Egcp.png =x300) ![image](https://hackmd.io/_uploads/HJ9QcEg56.png =x300)

----

## 仙人掌圖的定義

仙人掌圖有很多可能的定義，根據題目給定

- 每條邊在恰好一個簡單環上
- 每條邊在最多一個簡單環上

![image](https://hackmd.io/_uploads/r1md5Egcp.png =x300) ![image](https://hackmd.io/_uploads/Skrx3Ve9a.png =x300)

----

## 經典問題 --- 判斷一張圖是否為仙人掌圖

判斷每條邊是否在恰好一個環上

----

### 作法

DFS，用 stack 維護當前遍歷的節點，
走到重複的節點就回退，把這個環上的點都記錄+1。
( 環的起點不加，因為一個點可以在多個環上 )

如果有節點被記錄超過 1 則此圖不是仙人掌圖。
![image](https://hackmd.io/_uploads/BJH4xre9T.png =300x)
<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

![image](https://hackmd.io/_uploads/BkhI27xqp.png)

上圖答案為 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)$