Speical Graph & 0-1 BFS

Advanced Competitive Programming
2/16

  • Functional graph
  • Jellyfish graph
  • Cactus graph
  • 0-1 BFS

Functional Graph

有向圖，每個節點出度恰好 1

image

Functional Graph 的特性

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

Functional Graph 經典問題

Functional Graph 走 k 步

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

image

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

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

給一張 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

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

image 9e8b425e-c0b6-4e95-9837-77fba039d0da

無向圖的 functional graph

常見的題型為樹上 DP 題變成水母圖上去做

水母圖上最小點覆蓋，最大獨立集等等

ICPC 2020 台北站 F. Cable Protection

給一張水母圖，求最小點覆蓋。

把環上延伸出去的樹的 DP值/累積答案先算完，
再把剩下的 case 在環上合併

其中一個好的處理順序是從所有葉節點開始往環的方向 DP 回去
可以用 BFS 每次把 degree = 1 的點拔掉，
最後只會剩下環上的點而已

Cactus graph

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

image image

仙人掌圖的定義

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

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

image image

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

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

作法

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

如果有節點被記錄超過 1 則此圖不是仙人掌圖。
image
或者砸 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

image

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

Select a repo