NYoj 20 吝嗇的國度：樹上 DFS 求每節點父節點

題目建模

N 個城市，N-1 條邊連通 → **樹**。給定起點 S，對每個城市 i，輸出從 S 到 i 路徑上的**上一個城市**（即父節點），S 輸出 -1。

解法：以 S 為根建樹 + DFS

1. 鄰接表存圖（vector g[N]）。
2. vis[] 標記訪問，避免無向圖回溯死循環。
3. 遞歸 DFS：dfs(u) 中遍歷鄰居 v，若未訪問則 ans[v]=u; dfs(v)。
4. 最後按 1..N 輸出 ans[]。

代碼實現

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXN = 100005;
vector g[MAXN];
int ans[MAXN];
bool vis[MAXN];
int n;

void dfs(int u) {
    vis[u] = true;
    for (int v : g[u]) if (!vis[v]) {
        ans[v] = u;
        dfs(v);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int S; scanf("%d%d", &n, &S);
        for (int i=1;i<=n;++i) g[i].clear();
        for (int i=1;i1) printf(" ");
            printf("%d", ans[i]);
        }
        puts("");
    }
    return 0;
}

複雜度

• 時間：O(N) 每測試用例。
• 空間：O(N)。

鄰接表 + 遞歸 DFS 是樹上父節點查詢的標準模板，注意遞歸深度可能達 10^5，實際比賽可改用棧模擬或加大棧限制。