NYOJ 20 吝嗇的國度 - DFS 求父節點

問題描述

N 個城市，N-1 條路構成樹。給定起點 S，對每個城市 i，求從 S 走到 i 必須經過的上一個城市（即父節點），S 輸出 -1。

解法：以 S 為根 DFS

從 S 開始 DFS，記錄每個節點的父節點。對於鄰居 v，若未訪問，則父節點[v] = u，繼續 DFS。最終輸出父節點陣列。

代碼實現（C++）

#include 
using namespace std;
const int MAXN = 100010;
vector G[MAXN];
int parent[MAXN];
bool vis[MAXN];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, s; cin >> n >> s;
        for (int i = 1; i <= n; i++) { G[i].clear(); vis[i] = false; parent[i] = 0; }
        for (int i = 0; i < n-1; i++) {
            int a, b; cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        parent[s] = -1;
        dfs(s);
        for (int i = 1; i <= n; i++) {
            if (i > 1) cout << ' ';
            cout << parent[i];
        }
        cout << '\n';
    }
    return 0;
}

關鍵點

• 無向圖建雙向邊。
• DFS 遞歸深度可能達 100000，需增大棧或用迭代 DFS（C++ 通常能通過）。
• 輸出格式：空格分隔，行尾無空格。