一、學習目標

• 理解鄰接矩陣與鄰接表的差異：空間、時間、適用場合。
• 熟練無向/有向圖的遍歷模板（BFS/DFS，優先用疊代實作以避免遞迴棧）。
• 實戰：連通分量 & 補邊、有向環偵測與輸出、圖複製、連通分量計數。

二、觀念說明

圖的儲存：鄰接矩陣 vs 鄰接表

實務上預設用鄰接表：

int n; 
vector<vector<int>> g(n+1); 
// 無向邊 (u,v):
g[u].push_back(v); g[v].push_back(u);
// 有向邊 u→v:
g[u].push_back(v);

遍歷與 visited 時機

• BFS（無權最短路）：入隊即 visited[v]=true；第一次到達即最短。
• DFS（枚舉/結構判定）：入棧/入遞迴即標；需要後序時（例如子樹彙總、找回邊）要注意處理順序。

無向圖 vs 有向圖

• 無向圖：加邊要雙向；DFS 找環時要略過 v==parent[u] 的反向邊。
• 有向圖：常用顏色標記（0=白、1=灰、2=黑）找回邊（灰邊）→ 有環；或做拓撲排序（DAG 無環）。

三、CSES實戰演練

題目1:Building Roads

原題:
https://cses.fi/problemset/task/1666

題意：
給 n 個城市與 m 條道路（無向圖），請輸出最少需要新建幾條道路，並給出一組可行的道路清單，使整張圖變成連通。

解題思路（連通分量 + 代表點接成鏈）:

• 用 BFS/DFS 找出所有連通分量，為每個分量挑一個代表城市。
• 若有 k 個分量，只要建 k-1 條邊，按代表點依序相連即可把整圖連通。
• 這組解一定可行且邊數最小。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > g(n+1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<char> vis(n + 1, 0);
    vector<int> reps;
    queue<int> q;

    for (int s = 1; s <= n; s++) if (!vis[s]) {
        reps.push_back(s);
        vis[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < g[u].size(); ++i) {
                int v = g[u][i];
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }

    int k = (int)reps.size();
    cout << k-1 << "\n";
    for (int i = 1; i < k; i++) {
        cout << reps[i-1] << " " << reps[i] << "\n";
    }
    return 0;
}

題目2:Round Trip II

原題:
https://cses.fi/problemset/task/1678

題意：
給 n 點、m 條有向邊，若存在有向環，輸出一個環上的節點序列（首尾相同封環）；否則輸出 IMPOSSIBLE。

解題思路（顏色標記 + 疊代 DFS）:

• 顏色：0=未訪、1=在棧（灰）、2=已完成（黑）。
• 用顯式 stack記 (u, next-index)：遍歷 u 的鄰居；遇到 color[v]==1 的回邊，以 parent 回溯出環 v → … → u → v。
• 迭代版避免深遞迴棧。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
    }

    vector<int> color(n+1, 0), parent(n+1, 0), idx(n+1, 0);
    for (int s = 1; s <= n; s++) {
        if (color[s] != 0) continue;

        stack<int> st;
        st.push(s);
        color[s] = 1; parent[s] = 0; idx[s] = 0;

        while (!st.empty()) {
            int u = st.top();
            if (idx[u] >= (int)g[u].size()) {
                color[u] = 2; st.pop();
                continue;
            }
            int v = g[u][ idx[u]++ ];

            if (color[v] == 0) {
                color[v] = 1; parent[v] = u; idx[v] = 0;
                st.push(v);
            } else if (color[v] == 1) {
                // 回邊 u -> v，v 是祖先
                vector<int> cyc;
                int x = u;

                // 先收集 u -> ... -> v（沿 parent 往上）
                while (x != v) {
                    cyc.push_back(x);
                    x = parent[x];
                }
                cyc.push_back(v);

                // 反轉成 v -> ... -> u
                reverse(cyc.begin(), cyc.end());

                // 用回邊 u -> v 關閉環
                cyc.push_back(v);

                cout << (int)cyc.size() << "\n";
                for (int i = 0; i < (int)cyc.size(); ++i) {
                    if (i) cout << ' ';
                    cout << cyc[i];
                }
                cout << "\n";
                return 0;
            }
            // color[v] == 2：已完成，忽略
        }
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Find if Path Exists in Graph

原題:
https://leetcode.com/problems/find-if-path-exists-in-graph/

題意：
給 n、無向邊 edges、起點 source、終點 destination，判斷是否存在一條路徑從 source 到 destination。

解題思路（BFS）:
建鄰接表，從 source 做 BFS；能走到 destination 就回 true，否則 false。

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int> > g(n);
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1];
            g[u].push_back(v); g[v].push_back(u);
        }
        vector<char> vis(n, 0);
        queue<int> q;
        q.push(source); vis[source] = 1;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == destination) return true;
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i];
                if (!vis[v]) { vis[v] = 1; q.push(v); }
            }
        }
        return false;
    }
};

題目2:Island Perimeter

原題:
https://leetcode.com/problems/island-perimeter/

題意：
grid 中 1 是陸地、0 是水。只有 1 塊島（可能有湖），四向相鄰視為連通。求島的周長。

解題思路（線性掃描）:

• 每個陸地格貢獻 4；若它與下方相鄰也是陸地，周長 -2；與右方相鄰也是陸地，再 -2（因為共享邊）。
• 掃一遍即可。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int n = (int)grid.size();
        if (n == 0) return 0;
        int m = (int)grid[0].size();

        int peri = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] != 1) continue;
                peri += 4;
                if (i+1 < n && grid[i+1][j] == 1) peri -= 2; // 與下方共享
                if (j+1 < m && grid[i][j+1] == 1) peri -= 2; // 與右方共享
            }
        }
        return peri;
    }
};