首頁 教學 演算法

# 前言

接下來會先介紹一些名詞再來就是演算法，我會直接放題目並提到用什麼演算法解。

# 基本觀念與名詞

  • 有向圖與無向圖 (directed and undirected graph)：路徑有方向性的稱為有向圖，沒有方向性的只是連通起來稱為無向圖。
  • 無加權圖與加權圖 (unweighted and weighted graph)：路徑有權重的稱為加權圖 (加權不一定都是正的)，沒有加權的稱為無加權圖。
  • 路徑與環路：從一點經由某個邊到達另外一點這樣稱為路徑 (path)，若任兩點之間最多只有一條邊 (稱為 simple graph)。頭尾是相同的點的路徑則稱為環路 (cycle/circuit)。
  • 無向連通圖與連通區塊：一個無向圖中任意一點可以到達任意一點，就稱為無向連通圖 (connected graph)，否則稱為非連通圖 (disconnected graph)。有可能這個圖是一個部分一個部分的，單個的那一個部分就單獨為連通區塊 (無向)，所以把每個單獨的聯通區塊連起來就會回變成無向連通圖 (無向)。
  • 樹狀圖 (樹)：一個連通而無環路的圖稱為樹，如果是簡單圖 (兩點間只有一個邊)，則樹的邊數必然等於點數減一。樹中如有一點被指定為根 (root)，則稱為有根樹，否則是無根樹。看下圖的樹來對照名詞，有根樹通常把根 (1) 畫在最上方，對點 2 來說點 1 是他的 parent，點 4 跟點 5 是他的 child，沒有 child 的點我們稱為葉子 (4,5,6,7,8)。
              1
           /  |  \
          2   3   4
         / \ / \
        5  6 7  8
  • 有向圖的強連通：有向圖跟無向圖不一樣不是都有連起來等於是連通圖。一個有向圖中任意一點可以到達任意一點稱為強連通圖 (strongly connected graph)。
  • 點的分支度 (degree) 與鄰居：兩個點如果透過一個邊相連 (相鄰) 則稱為鄰居，無向圖上是互為鄰居，有向圖則要區分 in-neighbor 與 out-neighbor。鄰居的個數則為分支度 (degree)。同樣的，在有向圖上因為有方向 degree 要分為 in-degree 與 out-degree。

樹是圖論裡最重要的特殊結構，會在下一章 1-10 樹上演算法 獨立詳細介紹。

# BFS (Breadth First Search，廣度優先搜尋)

BFS 通常用來查找兩個點的距離，DFS 不能算起點到各點的距離但是可以查找兩個點是否連通。

# 例題：小畫家 (Painter)（TOI 練習賽）

給定一張高度為 H 像素、寬度為 W 像素的點陣圖 P，由上至下數來第 i 個、由左至右數來第 j 個的像素以 (i,j) 表示。(i,j) 的色彩編號為 Cij。小明用某繪圖軟體開啟點陣圖 P，使用軟體中的「填色色彩」功能：用滑鼠點擊 (Si,Sj)，所有與 (Si,Sj) 屬於同一個「連通區塊」像素的色彩編號均會轉換成指定的色彩 Z。對於影像 P 上任兩個上、下、左或右相鄰的像素 (i,j) 與 (i',j')（即 (i',j')∈{(i-1,j),(i+1,j),(i,j-1),(i,j+1)}），如果 Cij 和 Ci'j' 相同，則說 (i,j) 與 (i',j') 同屬於同一個「連通區塊」。

輸入格式：第一列有五個非負整數依序為 H, W, S, iSj 與 Z (1≤H, W≤5×10^2, 1≤Si≤H, 1≤Sj≤W, 0≤Z≤99)，表示原始點陣圖 P 的高度為 H 像素、寬度為 W 像素、用滑鼠點擊 (Si,Sj)，將該連通區塊的色彩改為色彩 Z。第 2 列到第 H+1 列代表原始點陣圖每個像素的原始顏色，每行都有 W 個非負整數，彼此以一個空白隔開；第 i+1 列的第 j 個數字表示 (i,j) 的色彩編號 Cij (0 ≤ Cij ≤ 99)。

輸出格式：請輸出 H 行，每一行有 W 個非負整數，彼此以一個空白隔開，表示「填入色彩」Z 之後的新點陣圖 P'。

輸入範例 1 輸出範例 1
1 5 1 3 3
1 0 0 0 1		 1 3 3 3 1

這一題只是判斷連通的區域，所以也可以用 DFS 做。

#include<bits/stdc++.h>
using namespace std;
#define N 520
int a[N][N]={0};
int diri[4]={-1,0,1,0};//direction
int dirj[4]={0,1,0,-1};
bool done[N][N]={0};
struct xy{
    int x,y;
};
int main(){
    int h,w,si,sj,z,temp;
    cin>>h>>w>>si>>sj>>z;
    z++;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>a[i][j];
            a[i][j]+=1;
        }
    }
    temp=a[si][sj];
    queue<xy> q;
    q.push({si,sj});// 初始化放入起點
    done[si][sj]=1;// 第一個點
    while(!q.empty()){//BFS
        auto e=q.front();
        q.pop();
        int x=e.x,y=e.y;
        a[x][y]=z;
        for(int i=0;i<4;i++){
            //done 是為了讓同個點不要被重複被放入
            if(!done[x+diri[i]][y+dirj[i]] &&
               a[x+diri[i]][y+dirj[i]]==temp){
                q.push({x+diri[i],y+dirj[i]});
                done[x+diri[i]][y+dirj[i]]=1;
            }
        }
    }
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++)
            cout<<a[i][j]-1<<" ";
        cout<<endl;
    }
}

這個程式要特別注意的地方就是 done 那個陣列，同個點被重複放入雖然不會出錯可是會超時 (TLE)。

# 例題：闖關路線（APCS）

某個闖關遊戲上有一隻神奇寶貝與兩個可控制左右移動的按鍵。神奇寶貝被安置在僅可左右移動的滑軌上。滑軌分成 n 個位置，由左到右分別以 0~n-1 表示。當遊戲開始時，神奇寶貝從位置 0 開始，遊戲的資訊包含 P、L 與 R 三個數字，其中 P 表示所須移至的目標位置，L 與 R 則分別表示每按一次左鍵或右鍵後，會往左或往右移動的格子數。此外，每一個位置 x 都應對應一個瞬間移動位置 S (x)；每一次按鍵後，神奇寶貝會先依據按鍵往左或右移動到某個位置 x，接著瞬間移動至 S (x)。某些點的瞬間移動位置等同原地點，也就是 S (x)=x，這些點稱為停留點。開始與目標位置都一定是停留點；此外，每個點的瞬間移動位置都一定是停留點 (除非超出界外)，也就是不會發生連續瞬間移動的情形。遊戲的目標是以最少的按鍵數操作神奇寶貝由開始位置到達目標位置，此外，在移動過程中不可以超過滑軌的範圍 [0, n-1]，否則算闖關失敗；某些點的瞬間移動位置也可能會超出滑軌的範圍，移動到這些點也會導致闖關失敗。

輸入格式：輸入有兩行，第一行有 4 個數字，第 1 個為 n，第 2 個為目標位置 P，第 3 個為 L，第 4 個為 R，後三個數字皆為小於 n 之正整數，且 2≤n≤1e6。第二行有 n 個整數，依序是各點的瞬間移動位置 S (0), S (1), …, S (n-1)，這些數字是絕對值不超過 1e8 的整數。

輸出：輸出到達目標位置所需的最少按鍵數，如果無法到達目標位置，則輸出 -1。

範例一輸入 範例一輸出
5 3 1 2
0 3 2 3 5		 2

範例一說明：位置區間 [0,4]，目標位置為 3，左鍵往左移動 1 格，右鍵往右移動 2 格。到達目標位置最少的按鍵數是 2 次：從起點 0 第一次按下右鍵會到達位置 2，因為 S (2)=2，因此停留在 2，第二次按下左鍵，會往左移一格到達 1，因為 S (1)=3，所以瞬間移動到 3，由於 3 是目標位置，所以就闖關成功了。

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
int a[N];
bool visit[N];
int main(){
    int n,p,l,r;
    cin>>n>>p>>l>>r;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]<0 || a[i]>=n)
            a[i]=n;
    }
    queue<pair<int,int>> q;
    q.push({0,0});//{now,dis}
    visit[0]=1;
    int buffer;
    while(!q.empty() && q.front().first!=p){
        auto v=q.front();
        q.pop();
        buffer=v.first-l;
        if(buffer>=0 && a[buffer]!=n && visit[a[buffer]]!=1){
            q.push({a[buffer],v.second+1});
            visit[a[buffer]]=1;// 放入 queue 的時候就要變成 1
        }// 否則可能會重複放入
        buffer=v.first+r;
        if(buffer<n && a[buffer]!=n && visit[a[buffer]]!=1){
            q.push({a[buffer],v.second+1});
            visit[a[buffer]]=1;
        }
    }
    cout<<q.front().second;
}

BFS 就向雷達一樣從中心向外擴張，所以最先碰到的一定是最近的距離 (邊沒有權重的情況)，一樣要特別注 visit[] 這個陣列，這個陣列沒有放對地方做判斷，很有可能程式就會超時，因為不會報錯所以要特別小心。

這一題就不能用 DFS 了，因為 DFS 不像 BFS 一樣是像雷達從中心向外擴張。如果硬要用 DFS 做那就稱做窮舉，把每一條路走過再判斷哪幾條路可以到終點，在判斷出可以到終點的最短那條，所以這種題目不適合用 DFS 做。前面講到遞迴跟窮舉的時候我常把函式名稱用 DFS 現在就知道原因了。

# DFS (Depth First Search，深度優先搜尋)

# 例題：小寶的著色問題（APCS）

小寶有個布娃娃，娃娃會變化。娃娃身上有一些圖案，這些圖案是由一些圓圈和一些線條組成，每個線條連接著某兩個不同的圓圈。小寶很喜歡著色，他決定要把這些圓圈塗上紅色或藍色，他覺得有線條相連的圓圈最好塗上不一樣的顏色，但是因為圓圈很多，他不知道能不能夠完成這樣的想法，請你幫他計算看看是否可以有辦法完成這樣的著色。

輸入格式：第一行有一個整數 T，代表接下來有 T 張圖的資料要計算。每張圖資料的第一行是兩個整數 n 與 m，代表有 n 個圓圈與 m 個線條，第二行有 2m 個整數，每兩個一組代表一根線條所連接的兩個圓圈編號，圓圈是以 0~n-1 編號。n 不超過 1e4，m 不超過 1e5。T 不超過 20。

輸出：依序每一行輸出一張圖是否可以正確著色，如果是，則輸出 yes，否則輸出 no。

範例一輸入 範例一輸出
2
2 0
4 3
0 3 3 2 2 0		 yes
no

範例說明：第一張圖 n=2, m=0，表示有兩個圓圈而沒有線條，可以正確著色。第二張圖有 4 個圓圈與 3 根線條，3 根線條是 (0,3)、(3,2) 與 (2,0)，這 3 個點如果只用 2 種顏色，不管如何上色都會有同色的相連。

這一題觀察一下也是判斷連通的問題，不會牽扯到距離，所以用 BFS 或 DFS 都可以，我程式是用 DFS 在遞迴式裡看起來蠻直覺的，通常情況可以的狀況下我偏好喜歡用 DFS 不過通常 BFS 會比用 DFS 快一點。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
int t,n,m,color[N];
vector<int> adj[N];
bool c;
void dfs(int p){
    for(auto e:adj[p]){
        if(color[e]==0){// 相鄰兩點必須不同色
            if(color[p]==1) color[e]=2;
            else color[e]=1;
            dfs(e);
        }else if(color[e]==color[p]){// 同色不合
            c=1;
            return;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        c=0;
        memset(color,0,sizeof(color));
        for(int i=0,u,v;i<m;i++){
            cin>>u>>v;// 無向圖兩邊都要連通
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int i;
        for(i=0;i<n;i++){
            if(color[i]==0)
                dfs(i);
            if(c) break;
        }
        if(c) cout<<"no\n";
        else cout<<"yes\n";
        for(i=0;i<n;i++) adj[i].clear();
    }
}

這題因為輸入數字比較多，所以必須要 I/O 加速，通常在考試或是比賽的時候都會直接多打那兩行來加速，我幾乎每打是因為不想占版面。這正是 1-1 提過的 ios::sync_with_stdio(0); cin.tie(0); 加速技巧。

這題本質是二分圖判定（bipartite check）：用兩種顏色交替染色，只要在染色過程中發現「相鄰兩點同色」就代表不是二分圖，無法完成著色。

# DAG 與 topological sort

DAG (directed acyclic graph)：有向無環圖

# 例題：AOV (Activity On Vertex) 最早完工時間（AP325）

某個計劃有 n 項工作，以 1~n 編號，工作之間有前置關係，我們用一個點代表一項工作，以邊 (a,b) 表示 a 是 b 的前置工作，也就是說 a 完成之後，工作 b 才能開始。每一項工作 v 有一個需求的工作時間 w [v]，代表工作至少需要耗時 w [v] 才能完成。

本題要計算此計畫的最早完工時間，也就是計畫開始後，最早可以完成所有工作的時間。此外，對於某個工作，如果該工作的任何延誤都會讓整個計畫的最早完工時間延後，這個工作就稱為關鍵工作，否則稱為非關鍵工作。請計算那些工作是關鍵工作。

舉例來說，n=3，前置關係有 (1,3) 與 (2,3)，代表工作 1 完成後才可以開始工作 3 的，相同的，工作 2 完成才可以開始工作 3。需求工時為 w [1]=1, w [2]=3, w [3]=4。我們可以看得出，工作 1 與 2 可以一起開始平行作業，在時間 1 時可以完成工作 1，時間 3 時可以完成工作 2，因此工作 3 最早可以開始的時間是 3，而最早的完工時間是 7。這三項工作中，工作 2 與 3 是關鍵工作，但工作 1 不是，因為工作 1 只要不花超過 3 的工時 (延誤超過 2)，並不會影響整個計劃的最早完工時間。

輸入格式：第一行是兩個正整數 n 與 m，代表工作數與前置關係數，點以 1~n 編號，第二行是 n 個正整數，依序代表每一個工作的需求工時 w [v]，接下來有 m 行，每行兩個整數 u 與 v，代表 u 是 v 的前置工作。n 不超過 1e4，m 不超過 1e5，w 不超過 1e3。輸入保證有解。

輸出：第一行輸出最早完工時間，第二行輸出那些工作是關鍵工作，輸出時依照工作的編號由小到大，相鄰兩數字之間以一個空白分格。

範例一輸入 範例一輸出
3 2
1 3 4
1 3
2 3		 7
2 3
範例二輸入 範例二輸出
4 4
1 2 3 4
1 2
1 3
1 4
3 4		 8
1 3 4

其實這題的解題思路主要先找到最早完工時間後再根據最早完工時間去找關鍵工作，觀察哪個工作的時間是前置工作時間最長的那他就是關鍵工作，可能不只有一個，如果兩個工作的工時都一樣，那就都是關鍵工作，這裡指的工時不是只指單個工作的工時而已，還要計算那個工作的前置時間才能算出完成那個工作的時間。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n,m,dis,w[N];
bool done[N],indeg[N];//in-degree 入度
vector<int> adj[N],ans;
set<int> st;
void f(int p){
    if(indeg[p]==0) return;
    int mx=0;//mx 的定義為時間最久的點
    for(auto e:adj[p]){
        f(e);
        if(w[mx]<w[e]) mx=e;
    }
    indeg[p]=0;
    w[p]=w[p]+w[mx];
    if(w[ans.front()]<w[p]){// 如果多個點花的時間一樣都要判斷關鍵工作
        ans.clear();
        ans.push_back(p);
    }else if(w[ans.front()]==w[p])
        ans.push_back(p);
}
void dfs(int p){// 如果多個點花的時間一樣都要判斷關鍵工作
    vector<int> mx;
    mx.push_back(0);
    st.insert(p);
    for(auto e:adj[p]){
        if(w[mx.front()]<w[e]){
            mx.clear();
            mx.push_back(e);
        }else if(w[mx.front()]==w[e])
            mx.push_back(e);
    }
    if(mx.front()!=0){
        for(auto e:mx) dfs(e);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=0,u,v;i<m;i++){
        cin>>u>>v;
        adj[v].push_back(u);
        indeg[v]=1;
    }
    ans.push_back(0);
    for(int i=1;i<=n;i++){
        if(indeg[i]==0) continue;
        f(i);
    }
    for(auto e:ans)// 如果多個點花的時間一樣都要判斷關鍵工作
        dfs(e);
    cout<<w[ans.front()]<<"\n";
    for(auto e:st)
        cout<<e<<" ";
}

# 另一種寫法：改用 out-degree

我用了兩種方式寫了這題，雖然大同小異，不過可以觀察不同的地方。

#include <bits/stdc++.h>
using namespace std;
#define N 10005
int n,m,outdeg[N];
vector<int> adj[N];
pair<int,bool> w[N];
set<int> criticalJobs;
void expre(int a,int b,vector<int>& v,int _i){// 如果多個點花的時間一樣都要判斷關鍵工作
    if(a < b){
        v.clear();
        v.push_back(_i);
    }else if(a == b){
        v.push_back(_i);
    }
}
int dfs_max(int p){// 找出最早完工時間
    if(w[p].second) return w[p].first;
    int mx=0;
    for(auto u:adj[p]){
        mx=max(mx,dfs_max(u));
    }
    w[p].second=1;
    return w[p].first+=mx;
}
void dfs_criticalJob(int p){// 找出關鍵工作
    vector<int> temp(1,0);
    for(auto u:adj[p])
        expre(w[temp.front()].first,w[u].first,temp,u);
    if(temp.front()==0) return;
    for(auto u:temp)
        criticalJobs.insert(u);
    for(auto i:temp)
        dfs_criticalJob(i);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i].first;
    for(int i=0,u,v;i<m;i++){
        cin>>u>>v;
        outdeg[u]++;
        adj[v].push_back(u);
    }
    vector<int> ans(1,0);
    for(int i=1;i<=n;i++){
        if(outdeg[i]!=0) continue;
        dfs_max(i);
        expre(w[ans.front()].first,w[i].first,ans,i);
    }
    cout<<w[ans.front()].first<<"\n";
    for(auto i:ans){// 最早完工時間可能有多個一樣
        criticalJobs.insert(i);
        dfs_criticalJob(i);
    }
    for(auto u:criticalJobs)
        cout<<u<<" ";
}

仔細看過程式碼後會發現兩程式主要就差在 indeg 跟 outdeg 這兩個變數，這兩種方法都能寫，程式跑的時間也差不多，所以就看習慣寫哪種就寫哪種都可以，我覺得我第二個程式寫的可讀性比較好，我把重複的地方拉出來寫成一個函式，這樣程式碼看起來就比較簡潔，我也不用打重複的東西打那麼多次。

下方的圖每個點上的數字代表那個工作的工時：

5 --> 2 \
4 --> 3 --> 1
3 --> 4 /

可以看到最右邊那個點有三個前置工作他的三個前置工作個別再加上他們各自的前置工作，總和剛好都是 7 所以這裡的每個工作都是關鍵工作，因為不能有任何一個工作延期這樣都會導致整體工時變長，所以最早完工時間是 8。

這題其實是 1-8 動態規劃 提過的「DAG 上的最長路徑」DP： dfs_max(p) 就是在算「以 p 結尾的最長路徑長度」，轉移式是 w[p] += max(所有前置工作的 w值) —— 這正是動態規劃在圖論裡最典型的應用場景，只是這裡子問題之間的依賴關係是由圖的邊決定的，而不是像陣列一樣是連續的索引。

# Dijkstra 演算法

# 例題：潛水 (Diving)（TOI 練習賽）

小軒是一個熱愛潛水的人，他趁著放暑假的時間去澎湖潛水。澎湖由許多小島組成，小軒今天想從 A 島經由潛水的方式到 B 島。潛水需要背著氧氣筒，而小軒不想浪費力氣去背過重的氧氣筒，他希望氧氣筒的容量夠用就好。小島間的距離有長有短，需要花費的氧氣量也不同，但有些島之間不能由潛水來移動；每抵達一座島就可以把氧氣筒重新裝滿。請你幫小軒算出他最少要背多少容量的氧氣筒才能讓他順利從 A 島潛水抵達 B 島。

輸入說明：第一列有兩個整數 N 與 M（2<=N<=500、0<=M<=N (N-1)/2），代表有 N 座小島以及 M 條潛水路徑，小島的編號為 0~N-1。接下去有 M 列，代表島與島之間移動所需花費的氧氣量；每列有三個整數，前兩個整數為島的編號，第三個整數為兩個島之間潛水移動需要的氧氣量 W (2<=W<=50000)，雙向所需要的氧氣量相等。最後一列有兩個整數 A 與 B，代表小軒想從 A 島潛水移動到 B 島。

輸出說明：請輸出小軒最少要背多少容量的氧氣筒，若從 A 島無法經由潛水移動到 B 島，請輸出 -1。

範例輸入 #1 範例輸出 #1
4 4
0 2 3
0 1 1
1 3 6
2 3 5
0 3		 5
範例輸入 #2 範例輸出 #2
5 6
0 1 1
0 2 2
1 3 4
3 2 5
4 2 6
3 4 7
0 4		 6 
#include<bits/stdc++.h>
using namespace std;
#define N 505
vector<pair<int,int>> adj[N];
int n,m,A,B,done[N],apcaity;// 容量
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0,u,v,w;i<m;i++){
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    cin>>A>>B;
    priority_queue<pair<int,int>> pq;
    pq.push({0,A});
    while(!pq.empty()){
        auto e=pq.top();pq.pop();
        int w=e.first,v=e.second;
        if(done[v]!=0) continue;
        done[v]=w;
        apcaity=min(apcaity,w);
        if(v==B) break;
        for(auto k:adj[v]){
            if(done[k.first]!=0) continue;// 不一定要
            pq.push({-k.second,k.first});
        }
    }
    if(done[B]==0) cout<<"-1";
    else cout<<-apcaity;
}

這一題必須要 I/O 優化才能通過所有的測資，因為這題的輸入比較多，一般來說在檢定或是比賽都會直接多打那兩行，我在這本講義幾乎都沒打只是因為覺得占版面而已，所以記得檢定的時候要記得打。

這一題觀察下來很像就是把 BFS 裡的 queue 換成 priority_queue 而已，確實也是這樣，因為要求權值小的所以在把數字放進 priority_queue 的時候改成負的，注意 priority_queue 裡面的 pair 記得要把權值放在 first 因為是根據 first 做判斷的，如果一樣就會看 second 不過這個特性在這裡不重要。

再來要注意的就是放進 priority_queue 裡的權值只是那一條路的權重而已這裡要特別注，別跟 prim 演算法搞混了。

# 例題：蓋步道（APCS，Dijkstra 的變形應用）

有一個大小為 n×n 的方形區域， h_ij 代表位於座標 (i,j) 的格子該處的海拔高度。工程團隊想要從該區域的左上角 (1,1) 鋪設一條步道到右下角 (n,n)，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。考量到行人在步道上行走的安全，必須要注意步道每一步之間的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。

輸入說明：第一行為一個數字 n (1≤n≤300)，代表該區域的大小。接下來有 n 行，第 i 行有 n 個正整數，每一個正整數 hij(1≤hij≤10^6) 代表該位置的海拔高度。

輸出說明：輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。

範例輸入 #1 範例輸出 #1
4
9 4 3 2
5 9 8 10
3 3 2 8
6 3 3 4		 4
6

這一題雖然不一定要用 Dijkstra 演算法可以用二分搜查找最大高度差的最小值，可是我還是來練習練習用 Dijkstra 演算法。

#include<bits/stdc++.h>
using namespace std;
#define N 305
int a[N][N],d[4][2]={{-1,0},{0,1},{1,0},{0,-1}},n;
int dis[N][N];
int Dijkstra(){
    priority_queue<vector<int>> q;
    q.push({0,1,1});
    while(!q.empty()){
        auto e=q.top();
        q.pop();
        if(e[1]==n && e[2]==n) return -e[0];// 終止條件
        if(dis[e[1]][e[2]]) continue;// 防止走回頭路
        dis[e[1]][e[2]]=1;
        for(int i=0;i<4;i++){
            int r=e[1]+d[i][0],c=e[2]+d[i][1];
            if(!dis[r][c]){
                q.push({min(e[0],
                            -abs(a[r][c]-a[e[1]][e[2]])),r,c});
            }
        }
    }
    return -1;// 除錯用的正常情況程式不會跑到這裡
}
int bfs(int h){
    queue<pair<int,int>> q;
    q.push({1,1});
    memset(dis,0,sizeof(dis));
    dis[1][1]=0;
    while(!q.empty()){
        auto e=q.front();
        q.pop();
        int x=e.first,y=e.second;
        if(x==n && y==n) return dis[n][n];// 終止條件
        for(int i=0;i<4;i++){
            int r=x+d[i][0],c=y+d[i][1];
            if(dis[r][c]==0 && abs(a[r][c]-a[x][y])<=h){
                dis[r][c]=dis[x][y]+1;
                q.push({r,c});
            }
        }
    }
    return -1;// 除錯用的正常情況程式不會跑到這裡
}
int main(){
    cin>>n;
    for(int i=0;i<=n+1;i++){
        a[0][i]=a[i][0]=a[n+1][i]=a[i][n+1]=1e9;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    int k=Dijkstra();// 查找最大高度差的最小值
    cout<<k<<"\n"<<bfs(k);
}

這題的巧妙之處在於把 Dijkstra 的「最小化路徑總和」改成「最小化路徑上的最大邊權」：優先佇列裡存的不是累計距離，而是「目前路徑上出現過的最大高度差」，每次擴展時用 min(目前的最大值, 新邊的高度差) 更新 —— 這保證了第一次抵達終點時，得到的就是「最大高度差最小」的方案。找到這個最小的最大高度差之後，再用一次 BFS（在「高度差 ≤ 這個值」的限制下）找最短路徑長度。

這是 Dijkstra 演算法一個很有啟發性的變形：只要「合併路徑上的邊權」這個運算滿足某種單調性，Dijkstra 的貪心策略（每次取出目前最優的點）依然成立，不一定要是加總。

# 併查集 (Union and Find)

以前我對於並查集跟 DSU 這兩個名詞有點搞混，所以我這邊來解釋一下。

Union-Find（合併查找）和 DSU（Disjoint Set Union，不相交集合）是相關的概念，通常在演算法中用於處理集合的合併和查找操作。

Union-Find 是一種資料結構，用於解決集合合併和查找問題。它可以高效地處理合併（Union）和查找（Find）兩種操作，並且常用於解決圖論和連通性問題。Union-Find 的主要目標是維護一組不相交的集合，每個集合由一個代表元素表示。它提供了合併兩個集合和查找元素所屬集合的代表元素的操作。

DSU 是 Union-Find 的一種特殊情況，它主要關注的是處理不相交集合的合併操作。DSU 在一個集合中的每個元素都有一個指向同一集合的代表元素，用於表示元素之間的連接關係。它提供了合併兩個集合和查找元素所屬集合的操作，以及額外的功能，如查找集合的大小或計算集合之間的連通性。

# 例題：2316. Count Unreachable Pairs of Nodes in an Undirected Graph（LeetCode）

給定一個整數 n，有一個無向圖具有 n 個節點，編號從 0 到 n-1。給定一個二維整數陣列 edges，其中 edges[i] = [ai, bi] 表示節點 ai 和 bi 之間存在一條無向邊。請返回兩兩不可從彼此到達的不同節點對的數量。

限制：1 <= n <= 1e5，0 <= edges.length <= 2×1e5，edges [i].length == 2，0 <= ai, bi < n，ai != bi，沒有重複的邊。

輸入 輸出
n = 3, edges = [[0,1],[0,2],[1,2]] 0
n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]] 14

輸入一：三個點都能彼此到達所以輸出是 0。輸入二：有 14 對節點彼此無法到達，因此輸出為 14。

class Solution {
public:
    int find(int p,vector<int>& boss){
        return (boss[p]<0) ? p : boss[p]=find(boss[p],boss);
    }
    long long countPairs(long long n,vector<vector<int>>& edges)
    {
        vector<int> boss(100005,-1);
        long long sum;
        sum = (n)*(n-1)/2;
        for(auto &u:edges){
            int a=find(u[0],boss);
            int b=find(u[1],boss);
            if(a!=b){
                if(boss[a] > boss[b]) swap(a,b);
                sum-=boss[a]*boss[b];
                boss[a]+=boss[b];
                boss[b]=a;
            }
        }
        return sum;
    }
};

sum = (n)*(n-1)/2; 首先來解釋這行，所有點 * 所有點除了自己 / 2 (因為兩兩相對)。

int find(int p,vector<int>& boss){
    return (boss[p]<0) ? p : boss[p]=find(boss[p],boss);
}

上面這部分是查找點 p 的 boss， boss[p] 會一直更新這樣下次呼叫到他就會直接回傳 boss 的值不用再依序遞迴跑一次。註：這裡的 boss 不是指 vector 的名稱，是指這個集合的代表元素，只有代表元素的值都會是負的其他元素的值都會是正的且會指向代表元素。

這一段是所謂的路徑壓縮（path compression）：每次查找時，順便把沿路經過的所有點都直接指向根節點，這樣下次查找同樣的點就是 O(1) 。搭配下面合併時「按大小合併」的優化（union by size），Union-Find 的均攤時間複雜度可以逼近 O(1) （精確地說是反阿克曼函數 O(α(n)) ，實務上可以當常數看待）。

int a=find(u[0],boss);
int b=find(u[1],boss);
if(a!=b){
    if(boss[a] > boss[b]) swap(a,b);
    sum-=boss[a]*boss[b];
    boss[a]+=boss[b];
    boss[b]=a;
}

這部分是合併，首先查找 u [0] 跟 u [1] 這兩點的 boss，如果 boss 一樣就代表兩點在同一個集合裡就不用合併了，如果不同就代表兩個點在不同的集合現在要合併，再來看 boss 裡的值是誰的子集合比較小就合併到大的去，這裡要注意正負號，這兩個部分就是併查集的核心思想。

# 例題：紅白彩帶（APCS，併查集動態維護連通區塊長度）

一條彩帶被分成 n 個相同大小的格子，有的格子是紅色，有些則是白色。小軒拿到彩帶後開始塗顏色，每次會將一個白色格子塗滿紅色，然後小軒會算一算目前最長與最短紅色區域的長度佔了幾格，相鄰的紅色格子就屬於同一個紅色區域。小軒一共塗了 k 次，請你計算出每一次紅色區域的最大與最小長度，並輸出個別的總和。

彩帶可以看成一維陣列，以 0 表示白色，而 1 表示紅色。彩帶的格子從 1 開始由左而右依序編號，小軒每次將某個格子塗上紅色。

輸入格式：輸入有三行，第一行是兩個整數，依序是 n 與 k，代表彩帶長度以及小軒塗色的次數，n≤1e5、k≤2e4。第二行有 n 個 0 或 1 的數字，依序代表彩帶第 1 格至第 n 格的顏色，0 代表白色，1 代表紅色。第三行有 k 個數字，依序代表每一次塗紅色的格子編號，若 k=0，則第三行為空行。同一行數字之間都是以空白間隔。小軒每次一定塗在白色格子，而且紅色區域的長度不會超過 10100。

輸出：輸出兩行，第一行是每次紅色區域最大長度的總和，第二行是每次紅色區域最小長度的總和。

範例一輸入 範例一輸出
5 1
1 0 1 0 1
2		 4
2
範例二輸入 範例二輸出
9 3
0 1 1 0 0 1 0 1 0
5 1 7		 11
6

這一題是併查集動態維護連通區塊大小的經典應用：每次把一個白格塗紅，就跟左右相鄰（如果也是紅色）的區塊合併，合併後用一個 multiset 動態維護所有連通區塊的長度，就能快速取得目前的最大值跟最小值。

#include<bits/stdc++.h>
using namespace std;
#define N 101000
int n,k,a[N],boss[N],mx_ans,mn_ans;
multiset<int> mst;// 方便找最小值跟最大值
int find(int x){// 查找 boss
    return (boss[x]<0) ? x:boss[x]=find(boss[x]);
}
void Union(int x,int y){// 合併
    int g1=find(x);int g2=find(y);
    if(boss[g1]>boss[g2]) swap(g1,g2);// 注意正負號
    mst.erase(mst.find(-boss[g1]));// 原本值是負的加上負號變正的
    mst.erase(mst.find(-boss[g2]));
    boss[g1]+=boss[g2];
    boss[g2]=g1;
    mst.insert(-boss[g1]);
}
int main(){
    int temp;
    cin>>n>>k;
    fill(boss,boss+n,-1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1) mst.insert(1);
    }
    for(int i=1;i<n;i++){// 初始化
        if(a[i]==1){
            if(a[i-1]==1) Union(i-1,i);
        }
    }
    mx_ans=*mst.rbegin();
    mn_ans=*mst.begin();
    for(int i=0,idx;i<k;i++){
        cin>>idx;
        mst.insert(1);
        a[idx]=1;
        if(a[idx-1]==1){// 塗色後後方也是紅色就要合併
            Union(idx-1,idx);
        }
        if(a[idx+1]==1){// 塗色後前方也是紅色就要合併
            Union(idx+1,idx);
        }
        mx_ans+=*mst.rbegin();// 計算最大長度總和
        mn_ans+=*mst.begin();// 計算最小長度總和
    }
    cout<<mx_ans<<"\n"<<mn_ans;
}

這裡用 multiset 存的是「所有連通區塊的長度」（存負值方便配合 boss 陣列的表示法），每次合併時先把舊的兩個長度移除，再把合併後的新長度加回去，這樣 *mst.rbegin() 跟 *mst.begin() 就能 O(log n) 取得目前的最大跟最小連通區塊長度。這是併查集跟 1-1 提過的 multiset 結合使用的典型例子。

# 小結

這章走過了圖論最基本也最常用的幾個演算法：

演算法 用途 複雜度
BFS 無權圖的最短距離、連通性判斷 O(V+E)
DFS 連通性判斷、二分圖判定、走訪 O(V+E)
拓樸排序 / DAG DP 有依賴關係的排程、DAG 上的最長 / 最短路徑 O(V+E)
Dijkstra 有權圖（權重非負）的最短路徑 O((V+E) log V)
Union-Find 動態維護連通性、合併集合 近似 O(1) （均攤）

值得注意的是這些演算法常常會互相結合：DAG 上的最長路徑其實是 DP、蓋步道結合了 Dijkstra 跟 BFS、紅白彩帶結合了 Union-Find 跟 multiset。熟悉單一演算法只是第一步，真正的功力在於看出一道題目需要哪幾個技巧疊加起來用。

下一章要講樹上演算法 —— 樹是這章提過的最特殊的圖（連通且無環），因為結構更受限，可以用更精簡的方式做 DFS/BFS，也會出現一些樹狀圖特有的技巧。

# 練習題

（之後補上）