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)\) 的時間內做到
給一張 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 同時出發，
烏龜每次走一步，兔子每次走兩步。
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
給一張水母圖，求最小點覆蓋。
把環上延伸出去的樹的 DP值/累積答案先算完，
再把剩下的 case 在環上合併
其中一個好的處理順序是從所有葉節點開始往環的方向 DP 回去
可以用 BFS 每次把 degree = 1 的點拔掉，
最後只會剩下環上的點而已
Cactus graph
仙人掌圖，圖如其名，一球一球的
仙人掌圖的定義
仙人掌圖有很多可能的定義，根據題目給定
- 每條邊在恰好一個簡單環上
- 每條邊在最多一個簡單環上
經典問題 –- 判斷一張圖是否為仙人掌圖
判斷每條邊是否在恰好一個環上
作法
DFS，用 stack 維護當前遍歷的節點，
走到重複的節點就回退，把這個環上的點都記錄+1。
( 環的起點不加，因為一個點可以在多個環上 )
如果有節點被記錄超過 1 則此圖不是仙人掌圖。
或者砸 SCC/BCC 模版在判斷每個環是否為簡單環
出題法則
如果想把序列上的題目加難
\(\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 維護
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
- 延續剛剛走的繼續走，花費 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)\)