一、學習目標

• 了解 DFS 的兩種實作：遞迴與疊代（顯式 stack），何時該避免遞迴以防止棧爆。
• 掌握三個核心觀念：visited 標記、連通塊（connected components）、二分圖著色。

二、觀念說明

DFS 與 BFS 的定位

• DFS：一路往深處走，走不動再回頭（backtrack）。適合「整塊枚舉 / 結構判定 / 拓撲相關」：連通塊、二分圖、拓撲序、橋與割點、樹的性質（先序/後序）。
• BFS：分層擴張，保證無權圖的最短邊數路徑。適合最短步數、最近距離、擴散。

狀態表示與建圖

• 一般圖：用鄰接串列 vector<vector> g(n+1)；避免鄰接矩陣（記憶體 O(n²)）。
• 網格：把格子 (x,y) 視作節點，鄰居為 4/8 方向；檢查邊界與障礙。
• 增廣狀態：若有「鑰匙/方向/剩餘次數」等，節點需包含這些欄位（例如 (x,y,mask)），visited 也要對應到完整狀態。

visited 何時標？

• DFS（疊代/遞迴）：入棧/入遞迴時就標，避免重複推入。
• BFS：入隊即標，防止同層重複入隊。

遞迴 vs 疊代

• 遞迴碼短、好讀，但深鏈/大圖易棧爆（Windows/MinGW 常見）。
• 建議在競賽/線上評測用疊代（顯式 stack）版以穩定通過。

DFS 的三種「走法」順序（對樹/有根圖很實用）

• 前序（preorder）：到點就處理（常用於紀錄進點時間、建序列）。
• 中序（inorder）：二元樹特例。
• 後序（postorder）：處理完子樹再處理自己（常用於 DP on tree、統計子結果）。

時間戳與邊類型（進階）

• 在 DFS 中標 tin[u]/tout[u] 可做「祖先判定」：u 是 v 祖先 ⇔ tin[u] ≤ tin[v] ≤ tout[u]。
• 在有向圖：依 DFS 時間可分類樹邊/回邊/交叉邊，支撐一些證明與檢查（例如是否有環）。

典型應用速覽

• 連通塊（Rooms / Islands）：DFS/BFS 皆可；只要把整塊推平即可。
• 二分圖：DFS/BFS 著色判衝突。
• 拓撲排序（DAG）：DFS 後序反轉（或 Kahn）。
• 橋與割點：Tarjan 低連結值（low-link）。
• 樹上 DP / 直徑：後序彙總子結果、兩次 BFS/DFS 求直徑。

常見坑

• 忘了「入隊/入棧即標」，導致重複訪問 → TLE。
• 多組測資沒清 visited/color/parent。
• 狀態圖只標 (x,y) 卻沒把「狀態」納入 visited key。
• 網格回溯方向搞反；或越界判斷忘了等號。

三、CSES實戰演練

題目1:Round Trip

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

題意:
給一張無向圖（n 個點、m 條邊），請找出任意一個長度 ≥ 3 的環並輸出；若不存在則輸出 IMPOSSIBLE。

解題思路:

• 用 DFS 探索

  • visited[u]：是否看過
  • inStack[u]：是否在目前 DFS「路徑棧」上（用來判定回邊是否指向祖先）
  • parent[u]：DFS 樹中的父節點（用來重建環）

• 當處理 u 的鄰居 v：

  • 若 v == parent[u]，略過（無向圖的反向邊）
  • 若 !visited[v]，把 v 推進 DFS
  • 若 visited[v] && inStack[v]，發現 回邊 u → v（指向祖先 v），立刻以 parent 往上回溯：u → ... → v，並在尾端再加一個 v 收尾，得到一個閉合環

• 以 疊代版 DFS（顯式 stack） 實作，避免鏈狀圖遞迴棧溢位

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;

int n, m;
vector<int> g[MAXN];
int parentArr[MAXN];
char visited[MAXN]; //是否看過
char inStack[MAXN]; //是否在目前 DFS「路徑棧」上（用來判定回邊是否指向祖先）

bool find_cycle(vector<int>& cycle_out) {
    // 每個連通分量各跑一次
    vector<int> idx(n+1, 0); // 每個點鄰接表的掃描指標
    for (int s=1; s<=n; s++) {
        if (visited[s]) continue;

        stack<int> st;
        st.push(s);
        visited[s] = 1;
        inStack[s] = 1;
        parentArr[s] = 0;

        while (!st.empty()) {
            int u = st.top();

            // 如果這個點的鄰居都掃完，就彈出（結束 u 的遞迴）
            if (idx[u] >= (int)g[u].size()) {
                st.pop();
                inStack[u] = 0; // 離開當前遞迴路徑
                continue;
            }

            int v = g[u][ idx[u]++ ];

            if (v == parentArr[u]) continue; // 無向圖的反向邊

            if (!visited[v]) {
                visited[v] = 1;
                inStack[v] = 1;
                parentArr[v] = u;
                st.push(v);
            } else if (inStack[v]) {
                // 發現回邊 u -> v（v 是祖先）→ 重建一個環
                vector<int> cyc;
                cyc.push_back(v);
                int x = u;
                while (x != v) {
                    cyc.push_back(x);
                    x = parentArr[x];
                }
                cyc.push_back(v); // 收尾，首尾相同形成閉合環
                cycle_out.swap(cyc);
                return true;
            }
        }
    }
    return false;
}

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

    vector<int> cycle;
    if (!find_cycle(cycle)) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    cout << (int)cycle.size() << "\n";
    for (int i=0; i < (int)cycle.size(); ++i) {
        if (i) cout << ' ';
        cout << cycle[i];
    }
    cout << "\n";
    return 0;
}

題目2:Building Teams

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

題意:
給 n 點 m 無向邊，是否能把點分成兩隊，且每條邊兩端點在不同隊？若可，輸出每點所屬隊（1/2），否則 IMPOSSIBLE。

解題思路:

• 典型二分圖判定：對每個未著色節點啟動 DFS，將鄰居著相反色。若遇到同色衝突 → 不可行。
• 為避免深度過深，使用疊代 DFS（stack）著色。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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<int> color(n + 1, 0); // 0=未著色, 1/2=兩隊
    for (int s = 1; s <= n; ++s) if (color[s] == 0) {
        stack<int> st;
        st.push(s);
        color[s] = 1;

        while (!st.empty()) {
            int u = st.top(); st.pop();
            for (size_t i = 0; i < g[u].size(); ++i) {
                int v = g[u][i];
                if (color[v] == 0) {
                    color[v] = 3 - color[u]; // 1<->2
                    st.push(v);
                } else if (color[v] == color[u]) {
                    cout << "IMPOSSIBLE\n";
                    return 0;
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << color[i];
    }
    cout << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Number of Islands

原題:
https://leetcode.com/problems/number-of-islands/description/

題意:
'1' 表陸地、'0' 表水面，四向相鄰。求島嶼數量。
註:斜對角不算相連。

解題思路:
掃描網格，遇到 '1' 就啟動一趟 DFS，把整個連通陸地變為 '0'（或 visited），計數 +1。

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

        const int DX[4] = {-1, 1, 0, 0};
        const int DY[4] = {0, 0, -1, 1};

        int count = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (grid[i][j] != '1') continue;
                count++;

                stack<pair<int,int>> st;
                st.push(make_pair(i, j));
                grid[i][j] = '0';
                while (!st.empty()) {
                    pair<int,int> cur = st.top(); st.pop();
                    int x = cur.first, y = cur.second;
                    for (int k=0; k<4; k++) {
                        int nx = x+DX[k], ny = y+DY[k];
                        if (nx<0 || nx>=n || ny<0 || ny>=m) continue;
                        if (grid[nx][ny] != '1') continue;
                        grid[nx][ny] = '0';
                        st.push(make_pair(nx, ny));
                    }
                }
            }
        }
        return count;
    }
};

題目2:Max Area of Island

原題:
https://leetcode.com/problems/max-area-of-island/description/

題意:
同上，但要求回傳最大的連通陸地面積。

解題思路:
掃描網格，遇到 '1' 開 DFS 擴張累加面積，並把訪過的變 '0'；取所有連通塊中的最大值。

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

        const int DX[4] = {-1, 1, 0, 0};
        const int DY[4] = {0, 0, -1, 1};

        int best = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (grid[i][j] != 1) continue;

                int area = 0;
                stack<pair<int,int>> st;
                st.push(make_pair(i, j));
                grid[i][j] = 0;

                while (!st.empty()) {
                    pair<int,int> cur = st.top(); st.pop();
                    int x = cur.first, y = cur.second;
                    area++;
                    for (int k = 0; k < 4; ++k) {
                        int nx = x+DX[k], ny = y+DY[k];
                        if (nx<0 || nx>=n || ny<0 || ny>=m) continue;
                        if (grid[nx][ny] != 1) continue;
                        grid[nx][ny] = 0;
                        st.push(make_pair(nx, ny));
                    }
                }
                if (area>best) best=area;
            }
        }
        return best;
    }
};