changed 8 months ago  
Published Linked with GitHub

圖論

講師介紹

  • handle : the_coding_pooh / coding_pooh (基本上有 pooh 就是我啦)
  • 資讀負責被嗆的人
  • 講師裡面唯一沒有進過全國賽的 (希望今年能進)
  • Ina 的鐵粉

定義

先定義一些名詞 :

圖 Graph : 一個對 \(G(V,E)\)，\(V\) 是非空的集合，稱為點集，\(\forall v \in V\) 稱做點 (vertex)。 \(E\) 是一個對的集合，對裡每個元素都是點，\(\forall e \in E\) 稱做邊 (edge)。也會用 \(V(G)\) 表示一張圖的點集，\(E(G)\)表示邊集

子圖 Subgraph : 圖的某個子集，通常 \(H\) 是 \(G\) 的某個子圖記為 \(H \subseteq G\) ，有得時候只拔邊，有的時候還會拔點。

有向 / 無向 Directed / Undirected : \(e \in E(G)\) 是有序的還是無序的，或著說 \(uv\) 與 \(vu\) 是不是一樣的

重邊 Multiedge : 兩條重複的邊

自環 Loop : 起終點相同的邊

重圖 Multigraph : 允許有重邊的圖

近圖 Pseudograph : 允許有自環與重邊的圖

簡單圖 Simple Graph (我講圖應該都是指他) : 沒有自環與重邊的圖

路徑 Walk (Path) : 一個序列 \(v\) 滿足 \(\forall v_i \in V\)，且對所有\(1 \le i < n\) 存在邊 \(v_i v_{i + 1}\)

簡單路徑 (路徑) (Simple) Path : 一個點互斥的 Walk

行跡 Trail : 一個邊互斥的 Walk

(簡單) 環 (圈) (Simple) Cycle : \(v_1 = v_n\) 的 walk (path)

度數 Degree : 一個點連出去的邊數，計做 \(\deg(v)\) ，對於有向圖記 \(\deg_{in}(v), \deg_{out}(v)\) 為入度(連到的入邊數)與出度(連到的出邊數)。

連通 Connected (通常 for 無向圖) : 如果存在一條路徑起點是 \(v_1\) 終點是 \(v_2\) ，我們說 \(v_1\) 與 \(v_2\)連通 (\(v_1\) is connected with \(v_2\))

可抵達 Reachable (通常 for 有向圖) : 如果存在一條路徑起點是 \(v_1\) 終點是 \(v_2\) ，我們說 \(v_2\) 對 \(v_1\) 來講是可抵達的 (\(v_2\) is reachable from \(v_1\))

連通分量 / 連通塊 Connected Component (CC) : 一個包含一些連通的點與他們之間的所有在原圖上的邊的極大子圖。

鄰居 Neighbor (通常 for 無向圖): 對於 \(v\)，所有跟他有邊的 \(u\) 稱為他的鄰居，這個集合記為 \(\mathcal{N}(v)\)

圖的儲存

鄰接陣列 Adjacency Matrix

一個 \(\lvert V \rvert \times \lvert V \rvert\) 的 01 矩陣，通常記做\(A\)，\(A_{i,j}\) 帶表存在邊 \(ij\)

例如下面的矩陣:

\[ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix} \]

代表的就是下面這張圖:
Graph1

空間:\(O(\lvert V \rvert^2)\)

鄰接串列 Adjacency List

\(\lvert V \rvert\) 個 vector，第 \(i\) 個 vector 裡的元素 \(j\) 代表存在邊 \(ij\)

例如下面的鄰接串列:

\(1 : [2]\)
\(2 : [1]\)
\(3 : [1, 2]\)

代表的就是下面這張圖:
Graph1

空間:\(O(\lvert V \rvert + \lvert E \rvert)\)

我基本上只用這兩個，用到其他的時候再講。

圖的遍歷 Traversal

當還能繼續前進時就不 backtrack，一直到不能前進為止。

實作上通常用遞迴

void DFS(int nd){
	if(been[nd])
    	return;
    been[nd] = true;
	for(auto i:graph[nd]){
    	DFS(i);
    }
    return;
}

時間: \(O(\lvert V \rvert + \lvert E \rvert)\) \ \(O(\lvert V \rvert^2)\) (看怎麼存圖)
外加空間: \(O(\lvert V \rvert)\)

把所有相鄰且不在搜尋順序內的節點都丟入搜尋順序內，然後一直重複這個動作。

實作上一般用個 queue

void BFS(int rt){
	queue <int> order;
    while(!order.empty()){
    	for(auto i:graph[order.front()]){
        	if(!been[i]){
            	been[i] = true;
                order.push(i);
            }
        }
        order.pop();
    }
}

時間: \(O(\lvert V \rvert + \lvert E \rvert)\) \ \(O(\lvert V \rvert^2)\) (看怎麼存圖)
外加空間: \(O(\lvert V \rvert)\)

亂亂寫

void BFS(int rt){
	queue <int> order;
    while(!order.empty()){
        been[order.front()] = true;
    	for(auto i:graph[order.front()]){
        	if(!been[i]){
                order.push(i);
            }
        }
        order.pop();
    }
}

上面的 code 時間複雜度是?
worst case : \(\Omega (\lvert V \rvert \lvert E \rvert)\)

看完全圖的 case 就知道，每個人都會把邊號比他大的人丟進去 queue 一次，所以第一輪以後 queue 有 \(O(\lvert E \rvert)\) 個人，每個人又 check \(O(\lvert V \rvert)\) 個人。

那這樣呢?

void BFS(int rt){
    queue <int> order;
    while(!order.empty()){
        if(been[order.front()]){
            order.pop();
            continue;
        }
        been[order.front()] = true;
        for(auto i:graph[order.front()]){
            if(!been[i]){
                order.push(i);
            }
        }
        order.pop();
    }
}

時間是好的，外加空間從 \(O(\lvert V \rvert)\) 變 \(O(\lvert E \rvert)\)，不過這根本不是空間瓶頸，所以根本沒差。

DFS / BFS 妙用

極大簡單路徑(AGC 013 B - Hamiltonish Path)

給一張圖，要求你找出一條點數 \(\ge\) 2 的點互斥的 path \(P\)，且 \(\mathcal{N}(P_1) \subset P\), \(\mathcal{N}(P_n) \subset P\) (與兩端點相鄰的點都要在這條路徑內)。

首先我們發現如果只要求 \(\mathcal{N}(P_n) \subset P\) 的話那其實就是 dfs，那如果還要要求 \(\mathcal{N}(P_1) \subset P\) 就把兩次 dfs 的結果接起來就好了!
Code

找環 (Library Checker - Cycle Detection Directed / Undirected)

給一張有向 / 無向圖，要求找到一個環。

維護誰在 dfs stack 裡面，如果我們戳到一個在 dfs stack 裡的點 \(u\) 那就有環了。

Code - Directed
Code - Undirected

歐拉路徑 / 迴路 (CSES - Teleporters Path & Mail Delivery, Kattis - Eulerian Path)

先定義一下歐拉路徑 (其實是歐拉行跡) : 一個通過圖上每一條邊的 Trail
定義歐拉迴路 : 一個通過圖上每一條邊的 Edge Distinct Cycle

現在問題是給定一張有向/無向圖，叫你給出一格歐拉行跡/迴路。

我們先確定歐拉路徑 / 迴路存在的充要條件:
歐拉路徑存在 \(\iff\) 奇點數 = 0 / 2
歐拉回路存在 \(\iff\) 奇點數 = 0

對於有向圖:
歐拉路徑存在 \(\iff\) 只有一個點入出度差為 1，一個為 -1，剩下都為 0
歐拉回路存在 \(\iff\) 每個點入出度相同

大概的證明是 \((\Rightarrow)\) 都是 Handshaking Lemma, \((\Leftarrow)\) 都是數歸一下 (或用構解的) (真的喔)

那怎麼構呢 (又在構)。
大概的作法是允許一個點進去很多次，但一條邊只會看一次的 dfs 後序 (可以自己在腦中跑跑看想一想)。

大概的 code 如下。

void dfs(int nd){
    for (; cur[nd] < graph[nd].size(); cur[nd]++){
        if(!been[graph[nd][cur[nd]].sc]){
            been[graph[nd][cur[nd]].sc] = 1;
            dfs(graph[nd][cur[nd]].fs);
        }
    }
    path.push_back(nd);
    return;
}

好欸，實作一下吧!

Mail Delivery - Code
Teleporters Path - Code
Eulerian Path - Code (我拿 atcoder 當 Ideone)

算連通塊數 (CSES - Counting Rooms)

給你一張圖，問你它有幾個連通塊。

一次 dfs / bfs 會走完所有同一個連通塊的人，因此只需要看要花幾次才能讓所有人都被走到就好。
Code

不帶權最短路 (TIOJ 1085 - 三維迷宮問題)

給你一張圖跟起終點，要求輸出一條最短路徑。

BFS 是最短路欸，至於要輸出就記錄每個人是被誰丟進 queue 的就好了。
Code (去年寫的，好醜，但我愛 Atcoder)

更多題

No Judge - \(\min(\deg(v)) \ge 3\) 找偶環

給一張圖，保證 \(\forall v \in V, \deg(v) \ge 3\)，要求你找一個偶環。

先 dfs 出一條 path \(P\)，我們知道 \(\mathcal{N}(P_n) \subset P\)，挑 \(\mathcal{N}(P_n)\) 內任意三個不同的點 \(a,b,c\) ， WLOG 假設在 \(P\) 上 \(b\) 在 \(a,c\) 之間，\(a\) 在最前面，我們知道 \(P\) 上的 \(a\) 到 \(b\) 的路徑、\(b\) 到 \(c\) 的路徑、\(a\) 到 \(c\) 的路徑一定有一個長度是偶數，則 \(P_n\) 接到長度為偶數的這條路徑就是一個偶環了!

No Judge - IMO 1991 p4 改

給一張連通圖，要求你給出一種幫邊編號的方法，使每條邊上的編號都介於 \(1 \sim \lvert E \rvert\) 之間，且對於 \(\deg(v) \ge 2\) 的點，他的所有邊的編號的 gcd 要是 1。

每條邊的編號為他被 dfs 到的順序，那我們知道除了 dfs 的開頭以外每個度數大於 2 的點一定有兩條邊的編號是連續的，至於 dfs 的開頭因為有連到編號是 1 的邊，所以也是好的。

NTUCPC OJ 29

給你一張圖，詢問是否存在兩條不一樣的歐拉路徑。

先找到一條，然後把鄰接串列每個人 reverse，然後再跑一次，看兩個有沒有差。

更更更多可能沒這麼好玩的題

CSES - Labyrinth
CSES - Round Trip
CSES - Monsters
CSES - Round Trip II

ABC 049 D
ABC 245 F
ABC 351 D
ABC 361 E
ABC 361 G

樹 Tree

定義

樹是一張 :

  1. 連通
  2. 無環
  3. 任兩點存在一簡單路徑且是唯一簡單路徑
  4. \(\lvert E \rvert = \lvert V \rvert - 1\)

的圖，只要有 {3}, {1, 2}, {1, 4}, {2, 4} 就可以定義是一顆樹了。

一些名詞

下面我用 \(path(u,v)\) 代表 \(u, v\) 之間唯一簡單路徑的點集
樹根 root : 某個我們特別指定的節點，下面叫他 \(r\)
祖先 ancestor : 對一個節點 \(u\)，\(path(u,r)\) 稱為他的祖先
子樹 subtree : 對於一個節點 \(u\), \(u\) 的子樹是 \(subtree(u) = \{ v \vert u \in path(v,r) \}\)

父節點 parent : \(\mathcal{N}(u) \cap path(u,r)\) ，只會有一個人或沒有人 (根)
子節點 child : \(\mathcal{N}(u) \cap subtree(u)\) ，可能會有很多人
葉節點 leaf : \(\lvert subtree(u) \rvert = 1\) 的點 (或沒有子節點的人)

深度 depth : \(\lvert path(u,r) \rvert\)，或有的時候會定義是前面那個-1
樹高 height : \(\max(\lvert path(u,r) \rvert)\)，也就是最深的深度

以 CSES 樹為例:
image

root 是 1
5 的 ancestor 有 {1,3}, 3 的 subtree 有 {3, 4, 5}
3 的父節點是 1, 1 的子節點有 {2, 3}
{2,4,5} 是葉節點，3 的深度是 2，樹高是 3

特殊的儲存法

除了可以用上面那兩種存法，也可以開一個陣列，存每個人的父節點是誰。

有向無環圖 (DAG, Directed acyclic graph) & 拓撲排序 (Topological Sort)

DAG

DAG 是一種特別的有向圖，滿足不存在任意相異兩點 \(u,v\) 彼此對對方都是可抵達的。
例如下面這一張

image

拓撲排序

拓撲排序是一個點集的 permutation，滿足對於每個點 \(u\)，他可以抵達的點在這個 permutation 內都在他後面，這樣的 permutation 可能有好幾個。

例如:
image

就有 1234 跟 1324 兩種。

DFS

DFS 後序 reverse 就是拓排序了欸。

void DFS(int nd){
	been[nd] = 1;
	for(auto i:graph[nd]){
    	if(!been[i])
        	dfs(i);
    }
    topo.push_front(nd);
    return;
}

int main(){
    for(auto i:V){
    	if(!been[i]) 
        	DFS(i);
    }
}

BFS

BFS 每次把入度為 0 的人丟進去 queue，就是拓排序了欸。

void BFS(){
	queue <int> q;
    for(auto i:V){
    	if(!in_deg[i])
        	q.push(i);
    }
    while(!q.empty()){
    	topo.push_back(q.front());
        for(auto i:graph[q.front()]){
        	in_deg[i]--;
            if(!in_deg[i])
        		q.push(i);
        }
        q.pop();
    }
    return;
}

題目

CSES - Course Scheddle
CSES - Longest Flight Route
CSES - Game Routes
ABC 335 E
ABC 341 F
ABC 357 E

並查集 (DSU, Disjoint Set Union)

Library Checker - Union Find

我們想要一種資料結構，可以支援以下三個操作 :
\(\text{build set} (v)\) : 建造一個 set \(\{v\}\)
\(\text{check}(u, v)\) : 找到 \(u\) 跟 \(v\) 所屬的 set \(S_u, S_v\)，判斷是否 \(S_u = S_v\)
\(\text{union}(u,v)\) : 找到 \(u\) 跟 \(v\) 所屬的 set \(S_u, S_v\)，將所有 \(S_u\) 中的元素移除，並加入 \(S_v\)

要怎麼做呢?

我們先考慮暴力維護

分析一下:
\(\text{build set} (v)\) : \(O(1)\)
\(\text{check}(u, v)\) : \(O(1)\)
\(\text{union}(u,v)\) : \(O(\lvert S_u \rvert (\log \lvert S_u \rvert + \log \lvert S_v \rvert))\)

Worst Case : \(O(QN \log N)\)

吃爆 TLE

一點點小優化?

我們發現 \(\text{union}(u,v)\) 的影響與 \(\text{union}(v,u)\) 是相同的，因此我們可以在 \(\lvert S_v \rvert \le \lvert S_u \rvert\) 的時後改作後面的。

複雜度變
\(\text{build set} (v)\) : \(O(1)\)
\(\text{check}(u, v)\) : \(O(1)\)
\(\text{union}(u,v)\) : \(O(\min(\lvert S_u \rvert, \lvert S_v \rvert)(\log \lvert S_u \rvert + \log \lvert S_v \rvert))\)

這個操作我們稱之為啟發式合並

這是很厲害的優化嗎，是欸，因為我們發現每個大小為 \(k\) 的 set，合併出他的時間
\(T(k) \le 2T(\frac k 2) + O(k \log k)\)，套一下主定理就發現 \(T(k) \in O(k\log^2k)\)

因此複雜度變 \(O(N \log^2 N + Q)\)

AC 了欸

這跟圖論有什麼關係?

這個問題本質上就是
\(\text{build set} (v)\) : 建一個新的點
\(\text{check}(u, v)\) : 問 \(u\) 跟 \(v\) 是否在同一個連通塊內
\(\text{union}(u,v)\) : 將 \(u\) 跟 \(v\) 建邊

而利用這樣的觀點我們接下來可以更進一步優化。

還記得樹嗎

確認兩個人是否在同一個連通塊可以看成兩個人的樹根是不是同一個人，而兩個點建邊可以看成兩個人的根建邊，然後挑一個當根。

那這樣複雜度分析就變
\(\text{build set} (v)\) : \(O(1)\)
\(\text{check}(u, v)\) : \(O(depth(u) + depth(v))\)
\(\text{union}(u,v)\) : \(O(depth(u) + depth(v))\)

再套一次啟發式合並

我們現在每次合併，都是把點數較小的樹的根當作點數較的大的樹子節點，那麼大小為 \(k\) 的樹高 \(h(k) = \max(h(x), h(k - x) + 1) \ (x \ge \frac k 2)\)，那麼我們可以用強數歸證明 \(h(k) \in O(\log k)\)

那這樣複雜度分析就變
\(\text{build set} (v)\) : \(O(1)\)
\(\text{check}(u, v)\) : \(O(\log \lvert S_u \rvert + \log \lvert S_v \rvert)\)
\(\text{union}(u,v)\) : \(O(depth(u) + depth(v))\)

還可以更好?

這時可以套一個東西叫做路徑壓縮，也就是因為我們只在乎每個人的根，因此我們其實可以每次查詢樹根的時候同時把它的父節點改成樹根，這樣不會影響結果。

有趣的是只套路徑壓縮也是 \(\log\) 級的，但兩個一起套的話總複雜度會變 \(O(N\alpha (N))\)，\(\alpha\) 是反阿克曼函數(Inverse Ackermann Function)，增長極慢，在你走的到的人上基本上都小於4，好賺喔。

推導當自主練習

實作細節

把紀錄大小的陣列跟父節點的陣列壓在同一個，然後用正負號代表是紀錄大小還是父節點。

Code

有向的 DSU & 帶權的 DSU

如果不做啟發式合並的話，可以很好的維護邊上的有向關係，而且這些邊每條也都可以帶權，因此在某些為護位能 (有向邊權且路徑固定) 的問題就可以用 DSU 解決。

e.g. ABC 328 F

練習題

CSES - Counting Rooms
CSES - Road Construction
ABC 049 B
ABC 295 G

ABC 328 F
ADT 240625 G
TIOJ 1312
TIOJ 1448

最短路

其實是待權圖的 walk / path 權最佳化

我們先看對於可帶負權的有向 / 無向圖，對於一個給定點 \(u\) ，我們想要對於每個點 \(v\) 求得 \(dis(u,v)\)。

如果不存在負環，我們就知道這個 walk 的長度一定不超過 \(\lvert V \rvert\)。

Naive DP

因此很直觀的想法是用 dp ，\(dp[i][j] \equiv\) 路徑長 \(\le i\) 的 path 上，可以到 \(j\) 最短的距離。

\(dp[i][j] = \min_{\mathcal{N_{in}}(j)}(dp[i - 1][k] + w_{kj})\)，(relaxation)

我們知道了 \(i \le \lvert V \rvert\)，每個 \(i\) 做的轉移的複雜度是 \(O(\lvert V \rvert + \lvert E \rvert)\)，因此總複雜度是 \(O(\lvert V \rvert ^ 2 + \lvert V \rvert \lvert E \rvert)\)

同時我們知道如果超過 \(\lvert V \rvert\) 次還能鬆弛，就存在負環。

而且這個 dp 可以滾動欸，賺。

時間 : \(O(\lvert V \rvert ^ 2 + \lvert V \rvert \lvert E \rvert)\)
外加空間 : \(O(\lvert V \rvert)\)

Bottom Up 實作:

    for (int t = 0; t <= V + 1; t++){
        for (int i = 1; i <= V; i++){
            for(auto e:graph[i]){
                ch_max(dp[!(t & 1)][e.fs], dp[(t & 1)][i] + e.sc);
            }
        }
    }

驗 code 裸題 : Eolymp - Ford-Bellman

Bellman Ford

滾動微麻煩欸，我如果改成這樣呢?

    for (int t = 0; t <= V + 1; t++){
        for (int i = 1; i <= V; i++){
            for(auto e:graph[i]){
                ch_max(dp[e.fs], dp[i] + e.sc);
            }
        }
    }

是好的欸，因為雖然可能一次往後鬆弛很多人，但我們還是保證了 \(\lvert V \rvert\) 次內一定可以鬆弛的完。

而且可以只看邊，變這樣

    for (int t = 0; t <= V + 1; t++){
        for(auto e:graph){
            ch_max(dp[e.v], dp[e.u] + e.w);
        }
    }

時間 : \(O(\lvert V \rvert \lvert E \rvert)\)
外加空間 : \(O(\lvert V \rvert)\)

SPFA

偷懶做點小優化，如果只看上次有被鬆弛到的點的邊呢?

聽起來很像 BFS 吧，實作也很像，大概長這樣 :

queue <int> q;
q.push(s);
dis[s] = 0;
while(!q.empty()){
    int nd = q.front();
    q.pop();
    for(auto i:graph[nd]){
        if(dis[i.fs] > dis[nd] + i.sc){
            dis[i.fs] = dis[nd] + i.sc;
            if(!in_queue[i.fs]){
                in_queue[i.fs] = 1;
                q.push(i.fs);
            }
        }
    }
     in_queue[nd] = 0;
}

據說期望複雜度 \(O(\lvert V \rvert + \lvert E \rvert)\) ， 但 worst case 還是 \(O(\lvert V \rvert \lvert E \rvert)\)

實作 Code

Library Checker 卡好好喔，TLE

回歸 BFS

我們可以保證每個人第一次離開 queue 就是最短路徑的時間嗎?
如果 \(\forall w \in {0, 1}\) 的話，我們是不是可以用一個 deque 來維護呢?

是欸，這個東西稱為 01 BFS

實作大概長這樣 :

deque <int> zoBFS;
zoBFS.push_back(t);
while(!zoBFS.empty()){
	int nd = zoBFS.front();
    zoBFS.pop();
    if(been[nd])
    	continue;
    been[nd] = 1;
    for(auto i:graph[nd][0]){
        ch_min(dis[i], dis[nd]);
        zoBFS.push_front(i);
    }
    for(auto i:graph[nd][1]){
        ch_min(dis[i], dis[nd] + 1);
        zoBFS.push_back(i);
    }
}

時間 : \(O(\lvert V \rvert + \lvert E \rvert)\)
外加空間 : \(O(\lvert V \rvert)\)

Dial

那如果\(\forall w \in {0, 1, \dots, k}\) 的話，我是不是可以開 \(k\) 個 queue，然後每當一個 queue 是空的時候就換下一個，這樣就可以做一樣的事了欸!
時間 : \(O(k(\lvert V \rvert + \lvert E \rvert))\)
外加空間 : \(O(k\lvert V \rvert)\)

Dijkstra

Dial 的瓶頸是幫每個距離分開處理，但是其實我們要的只是每次找距離最近的人，所以我們其實只需要一個可以支援以下操作的資料結構 :
單點修改，全域找到最小值

這樣我們就可以在 \(O(\lvert V \rvert \text{find min} + \lvert E \rvert \text{modify})\) 的時間做完這個了。

一個很直觀的做法就是直接開陣列，全域找最小值就暴力迴圈跑，這樣是 : \(O(\lvert V \rvert^2 + \lvert E \rvert)\)

如果用線段樹或某種自平衡二元樹的化兩個操作都可以在 \(\log \lvert V \rvert\) 的時間內完成，總複雜度為 : \(O((\lvert V \rvert + \lvert E \rvert) \log \lvert V \rvert)\)

用一個 fibonacci heap 的話是 \(O(\lvert V \rvert \log \lvert V \rvert + \lvert E \rvert)\)，用 priority queue 的話則是 \(O((\lvert V \rvert + \lvert E \rvert) \log \lvert E \rvert)\)

實作 Code

Dijkstra vs. SPFA

可以注意到 Dijkstra 的結構跟 SPFA 十分相似，差異之處就只有 queue 換成 pq 而且同一個人要去鬆弛別人很多次而已，因此我們其實也可以換個角度來看 Dijkstra 的正確性:

Dijkstra 基於最短路徑上的人一定比端點早被鬆弛完，所以每此用距離最近的人去鬆弛別人一定是好的，或著是你可以說它是一種順序優化過的 Bellman Ford。

全點對最短路

\(\forall (u,v)\) 我們想要求 \(dis(u,v)\)，很 naive 的做法就是對每個點當源點跑單點源最短路。

naive 的做法

直接跑 \(\lvert V \rvert\) 次全點對最短路，時間是 \(O(\lvert V \rvert \text{shortest path})\)，也就是對於無負權圖，我們可以知道對於稀疏圖 \(O(\lvert V \rvert \lvert E \rvert \log \lvert E \rvert)\)，稠密圖 \(O(\lvert V \rvert ^3)\)

那有什麼在有負權下也可以運作的方法嗎?

Floyd Warshall

我們考慮 \(dp[i][u][v] \equiv\) \(u,v\) 之間除了 \(u,v\) 外路徑上的點編號都小於 \(i\) 的最短路徑長

那我們知道轉移就是 \(dp[i][u][v] = min(dp[i - 1][u][i] + dp[i - 1][i][v], dp[i - 1][u][v])\)

而且也可以滾動欸，好賺
時間 : \(O(\lvert V \rvert ^ 3)\)
空間 : \(O(\lvert V \rvert ^ 2)\)

範例 Code

但這個滾動就像我們 Bellman Ford 那邊提到的一樣，其實可以直接變成 \(dp[u][v] = min(dp[u][v], dp[u][i] + dp[i][v])\)

實作大概長這樣

for(int k = 1; k <= V ; k++){
	for(int i = 1; i <= V; i++){
    	for(int j = 1; j <= V; j++){
        	ch_min(fw[i][j], fw[i][k] + fw[k][j]);
        }
    }
}

Johnson

現在看另一個角度，如果我們可以把負邊給幹掉，豈不是很爽?

potential \(\Phi(u)\)，定義 \(w'_{uv} = w_{uv} + \Phi(u) - \Phi(v)\)，

然後這個 \(\Phi(u)\) 可以定義為先加一個超級源點 \(s\)，並對每個點加上邊權為 0 的邊 \(su\) ，那 \(\Phi(u)\) 就是 \(s\) 到 \(u\) 的最短距離。

為啥這樣 \(w'\) 就都非負了? 原因是因為 \(\Phi(v) \le \Phi(u) + w_{uv}\)，這件事是顯然的 (如果不成立的話就會被 \(u\) 鬆弛到)。因此我們可以先跑一次 Bellman Ford，然後再跑 \(\lvert V \rvert\) 次 Dijkstra 就好，\(O(\lvert V \rvert \lvert E \rvert \log \lvert E \rvert)\)。

題目

CSES - Shortest Routes I
CSES - Shortest Routes II
CSES - High Score
CSES - Flight Discount
CSES - Cycle Finding

ABC 280 F
ABC 287 H
ABC 335 E
ABC 342 E

最小生成樹 (MST, Minimum Spanning Tree)

最小生成樹 & 森林

對於一張帶權連通圖 \(G\) ，定義他的最小生成樹是一顆連通每個點且邊權和最小的。那類似的我們也可以定義最小生成森林 (每個連通塊的最小生成樹集合起來的森林)。

那要怎麼找到最小生成樹呢?

Kruskal

我們考慮一個很直觀的想法，對邊集按照邊權有小到大排序，接著按照這個順序加入邊，一旦加入這條邊會有環就不要加他。

實作

sort(edges.begin(), edges.end());
for(auto e:edges){
	if(merge(e.u, e.v))
    	MST.push(e);
}

時間複雜度 : \(O(\text{sort}(\lvert E \rvert) + \lvert E \rvert \alpha(\lvert E \rvert))\)

Boruvka

對於每個 set \(S\) (一開始都是單獨一個點)，我們找到這個 set 連出去的最小的邊，然後將兩端的 set 合併，直到剩下一個連通塊

複雜度

我們知道每一次 \(CC\) 至少會變一半，因此只需要做 \(\log \lvert V \rvert\) 次就好，又每一次都可以用 dfs / bfs 做完，因此總複雜度為 \(O((\lvert E \rvert + \lvert V \rvert) \log \lvert V \rvert)\)

實作:Code

Prim

維護的點集 \(S\) 一開始是空的，然後每次找到 連出去最小的邊，把另外一端的點丟進去這個點集，那這樣我們最後就會有一棵最小生成樹了!

聽起來跟誰很像呢? Dijkstra，所以基本上過程一模一樣，複雜度分析也是。
時間複雜度 : \(O((\lvert E \rvert + \lvert V \rvert) \log \lvert E \rvert)\), \(O(\lvert E \rvert + \lvert V \rvert ^2)\) (跟 dijkstra 一樣)

題目

CSES - Road Peparation
Code Fes 16 qual B pC
Code Fes 17 Final pJ
JAG 12 pC
ABC 355 F
ABC 364 F

連通分量

DFS-Tree & Tarjan Low Function

DFS Tree 顧名思義就是你先挑一個點當根來跑 DFS，然後 DFS 走到的邊我們就叫樹邊 (Tree Edge)，這棵樹就叫 DFS Tree，剩下的非樹邊會有三種狀況 :

  1. Forward Edge 前向邊 : 邊 \(uv\)， \(v\) 是 \(u\) 的子樹
  2. Back Edge 返祖邊 : 邊 \(uv\)， \(v\) 是 \(u\) 的祖先
  3. Cross Edge 交錯邊 : 邊 \(uv\)，\(u,v\) 沒有祖孫關係

這時應該可以發現在無向圖上是不可能存在 Cross Edge 與 Forward Edge 的，有向圖上則都有可能出現。

我們定義一個點的 \(\text{dfn}(u)\) (又稱 dfs order) 是他是第幾個被 dfs 到的點 (也就是 dfs 前序編號)，定義 Tarjan low function \(\text{low}(u)\) 是所有 \(u\) 的子孫可以透過一條邊 (不論是否是 Tree Edge) 可以到的點的最小的 \(\text{dfn}\) ，也就是 \(\text{low}(u) = \min(\{\text{dfn}(x) | x \in \mathcal{N}(v), v \in \text{subtree}(u) - \{u\} \})\)。

這個東西的用途非常多，有趣的是當在無向圖上，我們只關心祖孫關係之間的 \(\text{low}\) 的相對關係時，\(\text{dfn}\) 可以用 \(\text{depth}\) 替代。

點雙連通分量 BCC-V (Bi-connected Component - Vertex)

定義

如果對於一個連通的點集 \(S\) 若移除任意一個元素 \(u\) 都還是連通，我們稱極大的這個點集 \(S\) 為一個點雙連通分量。

反之我們定義割點 (AP, Articulation Points) 為所以移除此點後圖就不連通的點。

性質

  1. 一個非 AP 最多只會在一個 BCC - V 內。

  2. 兩點 \(u,v\) 在同一個 BCC - V \(\iff\)移除非此兩點的任意點都無法使這兩點不連通

  3. 兩點 \(u,v\) 在同一個大於三個點的 BCC - V 中 \(\iff\) 存在一簡單環通過 \(u,v\)

  1. 兩點 \(u,v\) 在同一個 BCC - V 中 \(\iff\) 存在兩條除了端點外點互斥的路徑

  2. 三點 \(a\),\(b\),\(c\) 在同一個 BCC - V 中 \(\iff\)此三點任意順序都存在一簡單路徑依序過這三點

  3. 將每個 BCC - V 創一個虛點後，將 BCC - V 上的人連到這個虛點，這樣建出來的圖是一棵樹

怎麼找一個?

觀察到對於不是根的點 \(u\)，如果 \(\text{low}(u) \ge \text{dfn}(u)\) (可以用 depth 代替)，這個點很明顯是 AP，而且這個條件是若且唯若的，證明大概是因為拔掉 \(u\) 以後 \(u\) 的小孩與根的連通性就受上面那個條件決定了。

而對於根，如果只有一個子樹就不是 AP，否則就是。

實作 Code:

void Tarjan(int nd, int rt){
    been[nd] = 1;
    depth[nd] = depth[rt] + 1;
    low[nd] = depth[nd];
    
    dfs_stack.push_back(nd);

    int cnt = 0;

    bool flag = 0;

    for(auto i:graph[nd]){
        if(i == rt && !flag){
            flag = 1;
            continue;
        }
        if(been[i])
            low[nd] = min(low[nd], depth[i]);
        else{
            cnt++;
            Tarjan(i, nd);
            low[nd] = min(low[i], low[nd]);
            if(low[i] >= depth[nd]){
                BCC_ptr++;
                while(dfs_stack.back() != i){
                    BCC[BCC_ptr].push_back(dfs_stack.back());
                    dfs_stack.pop_back();
                }
                BCC[BCC_ptr].push_back(i);
                dfs_stack.pop_back();
                BCC[BCC_ptr].push_back(nd);
            }
        }
    }
    if(!cnt && rt == N + 1){
        BCC_ptr++;
        BCC[BCC_ptr].push_back(nd);
    }
    return;
}

這裡是用 depth 代替 dfn

時間複雜度 : \(O(\lvert V \rvert + \lvert E \rvert)\)

邊雙連通分量 BCC-E (Bi-connected Component - Edge)

定義

如果對於一個連通的點集 \(S\) 若移除任意一條邊 \(u\) 都還是連通，我們稱極大的這個點集 \(S\) 為一個邊雙連通分量。

反之我們定義橋 (Bridge) 為所以移除此邊後圖就不連通的邊。

性質

  1. \(u,v\) 同在一個 BCC - V 內且此 BCC - V 有 3 個以上的點 \(\implies\) \(u,v\) 在同一個 BCC - E 內

下面的性質則與 BCC - V 大多相似，證明也類似 :

  1. 兩點 \(u,v\) 在同一個 BCC - E \(\iff\)移除任意邊都無法使這兩點不連通

  1. 任意非橋的邊存在一簡單環包含他

  2. 兩點 \(u,v\) 在同一個 BCC - E 中 \(\iff\) 存在兩條邊互斥的路徑

  3. 將每個 BCC - E 縮成一個虛點後，建出來的圖是一棵樹

怎麼找一個?

觀察到對於不是根的點 \(u\)，如果 \(\text{low}(u) = \text{dfn}(u)\) (可以用 depth 代替)，這個點很明顯是橋的下端點，而且這個條件是若且唯若的，證明大概是因為拔掉邊 \(u, \text{par}(u)\) 的小孩與根的連通性就受上面那個條件決定了。

實作大部分根 BCC - V 很像。
實作 Code:

void Tarjan(int nd, int rt){
    been[nd] = 1;
    depth[nd] = depth[rt] + 1;
    low[nd] = depth[nd];
    dfs_stack.push_back(nd);

    bool flag = 0;

    for(auto i:graph[nd]){
        if(!flag && i == rt)
            flag = 1;
        else if(been[i])
            low[nd] = min(low[nd], depth[i]);
        else{
            Tarjan(i, nd);
            low[nd] = min(low[nd], low[i]);
        }
    }

    if(low[nd] == depth[nd]){
        BCC_ptr++;
        while(dfs_stack.back() != nd){
            BCC[BCC_ptr].push_back(dfs_stack.back());
            dfs_stack.pop_back();
        }
        BCC[BCC_ptr].push_back(dfs_stack.back());
        dfs_stack.pop_back();
    }
    return;
}

這裡是用 depth 代替 dfn

強連通分量 SCC (Strongly Connected Component)

定義

如果對於一個點集 \(S\) 滿足任意兩元素 \(u,v\) 是互相 reachable 的，我們稱極大的這個點集 \(S\) 為一個強連通分量。

性質

將每個 SCC 縮起來後得到的圖會是 DAG，且每個 SCC 裡都有一個有向環
其他真的沒什麼好講的

怎麼找一個?

觀察到如果一個人已經離開了 dfs stack，那你跟他就沒有機會在同一個 SCC 內，所以我們只關心還在 dfs stack 內的人，而如果出現了 \(\text{low}(u) = \text{dfn}(u)\) 就代表現在在 stack 上的人是一個 SCC 了，注意這裡的 \(\text{dfn}\) 不能用 depth 代替，不然 cross edge 會出大事。

實做:

void Tarjan(int nd){
    dfn[nd] = ++now_dfn;
    low[nd] = dfn[nd];
    been[nd] = 1;
    in_stack[nd] = 1;
    dfs_stk.push_back(nd);

    for(auto i:graph[nd]){
        if(!been[i]){
            Tarjan(i);
            low[nd] = min(low[nd], low[i]);
        }
        else if (in_stack[i])
            low[nd] = min(low[nd], dfn[i]);
    }

    if(low[nd] == dfn[nd]){
        scc_amnt++;
        while(dfs_stk.back() != nd){
            in_stack[dfs_stk.back()] = 0;
            scc_num[dfs_stk.back()] = scc_amnt;
            dfs_stk.pop_back();
        }
        in_stack[dfs_stk.back()] = 0;
        scc_num[dfs_stk.back()] = scc_amnt;
        dfs_stk.pop_back();
    }
    return;
}

Kosaraju

Kosaraju 是一個實做簡單但正確性較 Tarjan 不直覺得 SCC 算法，實作是先在正圖上獲得 dfs 後序 (離開點的順序)，這跟拓排序十分相似，如果此圖是 DAG 的話就就是拓排序了，接著在依照這個順序的 reverse 在反圖上跑 dfs，每次 dfs 到的人就是同一個 SCC 內的了。

實作:

void dfs(int nd, bool is_rev){
    been[nd] = 1;
    for(auto i:graph[nd][is_rev]){
        if(!been[i])
            dfs(i, is_rev);
    }
    path[is_rev].push_back(nd);
}

void Kosaraju(int N){
    for (int i = 1; i <= N; i++){
        if(!been[i])
            dfs(i, 0);
    }
    been.reset();
    reverse(path[0].begin(), path[0].end());
    for(auto i:path[0]){
        if(!been[i]){
            dfs(i, 1);
            scc_amnt++;
            for(auto j:path[1]){
                scc_num[j] = scc_amnt;
            }
            path[1].clear();
        }
    }
    return;
}

時空都與 Tarjan 相同。

有趣的是，Kosaraju 幫 SCC 編號的順序是拓排序，Tarjan 是拓排逆序。

K 連通分量 (KCC - V / E)

顧名思義就是需要移除至少 K 個點 / 邊才能讓他不連通，要怎麼做呢?
跑 flow 找最小割就知道是幾連通了。

K = 3 的話是線性的，用某種魔改的 low 去找 cut pair
可以看看

題目

CSES - Coin Collector
CSES - Necessary Roads
CSES - Necessary Cities
TIOJ 1910
Library Checker - Strongly Connected Components
Library Checker - Two-Edge-Connected Components
Library Checker - Three-Edge-Connected Components
Library Checker - Biconnected Components

環

3 Cycle

Detection

一個很值觀的想法是枚舉所有有邊的 \(u\),\(v\)，用 bitset 兩個 and 起來，複雜度為 \(O(\frac {\lvert E \lvert \lvert V \lvert} w)\)。

再來你知道對於鄰接矩陣 \(A\)，拿 \(A\) 去 or \(A^2\) 就可以知道有沒有了，所以你有 \(O(\lvert V \rvert ^ {\omega})\)

然後你 hybrid 一下，對於 \(\deg \le \Delta\) 的你就用 \(O(\Delta \lvert E \rvert)\) 的時間枚舉一條邊跟他的一端要連誰，所以只剩三個點 \(\deg > \Delta\) 的三角形，那你知道這樣點數有 \(O(\frac {\lvert E \rvert} \Delta)\)，複雜度是 \(O(({\frac {\lvert E \rvert} \Delta})^\omega)\)，總複雜度是 \(O(({\frac {\lvert E \rvert} \Delta})^\omega + \Delta \lvert E \rvert)\)，取 \(\Delta = {\lvert E \rvert} ^ {\frac {\omega - 1} {\omega + 1}}\) 可得 \(O(\lvert E \rvert ^ {\frac {2 \omega} {\omega + 1}})\)

On k - Cycle Finding Problem

你知道了你有一個 \(\tilde O(\lvert V \rvert ^ {\omega})\) 的演算法確認任意 \(k\) 環的存在性 (\(k \ge 3\), \(k \in O(1)\))

然後我們其實有個很重要的結論，找到定向特定長度偶環與找到特定長度奇環跟比找三角形難，找特定長度偶環則較為簡單。

4 - Cycle

Detection

枚舉 \((i,j)\) 有幾個中繼點，\(O(\lvert V \rvert ^2)\)

Maximum Density

用柯西壓一下，\(\Theta (\lvert V \lvert ^{1.5})\)

Erdos Theorem

\(C_{2k}\) has at most \(O(\lvert V \rvert ^{1 + 1 / k})\) edges.

建模

講師備課燒雞，用板書

2 - SAT

差分約束

擴展域 DSU

同餘最短路

偷渡優化建圖

題單

CF 1270 G

CF 1215 F

CF 1904 F

CF 786 B

CF 1770 D

TIOJ 1408

TIOJ 2289

ABC 302 H

ABC 232 G

ARC 048 B

Select a repo