UVA Firetruck：DFS 字典序輸出消防站到火場所有簡單路徑

題目大意

消防站位於路口 1，火場位於路口 k（k ≤ 20）。給定開放街道（無向圖），求從 1 到 k 的所有簡單路徑（不重複經過路口），按字典序輸出，並統計總數。
多測資，每測資以 0 0 結束，輸入以 0 開頭結束。

核心觀察：字典序 DFS

圖節點 ≤ 20，路徑數可控。
按字典序輸出 = 遞歸時按節點編號升序嘗試鄰居。
DFS 參數：dfs(cur, path)，path 記錄當前路徑。
到達 k 時輸出路徑並計數。
回溯時撤銷訪問標記。

優化：從終點反向 DFS 可達性剪枝

先從 k 反向 DFS/BFS 標記所有能到達 k 的節點 reachable[]。
正向 DFS 時，若 !reachable[next] 直接跳過，大幅減少無效搜索。

完整 C++ 實作

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 25;
int adj[MAXN][MAXN];
bool reachable[MAXN];
bool vis[MAXN];
int path[MAXN], pathLen;
int k, caseNo = 1;

void dfsReachable(int u) {
    reachable[u] = true;
    for (int v = 1; v <= 20; ++v)
        if (adj[u][v] && !reachable[v]) dfsReachable(v);
}

void dfs(int u) {
    vis[u] = true;
    path[pathLen++] = u;
    if (u == k) {
        for (int i = 0; i < pathLen; ++i) {
            if (i) printf(" ");
            printf("%d", path[i]);
        }
        putchar('\n');
    } else {
        for (int v = 1; v <= 20; ++v)
            if (adj[u][v] && !vis[v] && reachable[v])
                dfs(v);
    }
    --pathLen;
    vis[u] = false;
}

int main() {
    while (scanf("%d", &k) == 1 && k) {
        memset(adj, 0, sizeof(adj));
        int a, b;
        while (scanf("%d%d", &a, &b) == 2 && (a || b))
            adj[a][b] = adj[b][a] = 1;

        memset(reachable, 0, sizeof(reachable));
        dfsReachable(k);

        memset(vis, 0, sizeof(vis));
        pathLen = 0;
        int total = 0;

        printf("CASE %d:\n", caseNo++);
        dfs(1);

        // 重新跑一次計數（或在 dfs 中全局計數）
        // 這裡簡化：再跑一次只計數
        function countDfs = [&](int u) {
            vis[u] = true;
            if (u == k) ++total;
            else for (int v = 1; v <= 20; ++v)
                if (adj[u][v] && !vis[v] && reachable[v]) countDfs(v);
            vis[u] = false;
        };
        memset(vis, 0, sizeof(vis));
        countDfs(1);

        printf("There are %d routes from the firestation to streetcorner %d.\n", total, k);
    }
    return 0;
}

關鍵實作細節

• 字典序保證：鄰居迴圈 for(v=1; v<=20; ++v) 升序遍歷，自然產生字典序路徑。
• 可達性剪枝：dfsReachable(k) 標記所有能到達終點的節點，DFS 時跳過不可達節點。
• 路徑存儲：path[] 數組 + pathLen，避免 vector 拷貝開銷。
• 輸出格式：CASE N:、路徑空格分隔、統計行固定格式。
• 多測資處理：while(scanf("%d",&k)==1 && k)，每測資重置所有陣列。

複雜度分析

• 節點 ≤ 20，最大簡單路徑數指數級但實際受圖稀疏度限制。
• 可達性剪枝後搜索空間極小，UVA 判題機通過無壓力。
• 時間 O(路徑數 × 路徑長)，空間 O(V²)。

樣例驗證

Input:
6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0
0

Output:
CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.