<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)$
{"title":"Functional Graph & 01 BFS","contributors":"[{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":5097,\"del\":239},{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":59,\"del\":57}]","description":"Advanced Competitive Programming2/16"}
    989 views
   Owned this note