吝啬的國度 時間限制：1000 ms | 內存限制：65535 KB 難度：3 描述 在一個吝啬的國度裡有N個城市，這N個城市間只有N-1條路把這個N個城市連接起來。現在，Tom在第S號城市，他有張該國地圖，他想知道如果自己要去參觀第T號城市，必須經過的前一個城市是幾號城市（假設你不走重復的路）。 輸入 第一行輸入一個整數M表示測試數據共有M(1<=M<=5)組 每組測試數據的第一行輸入一個正整數N(1<=N<=100000)和一個正整數S(1<=S<=100000)，N表示城市的總個數，S表示參觀者所在城市的編號 隨後的N-1行，每行有兩個正整數a,b(1<=a,b<=N)，表示第a號城市和第b號城市之間有一條路連通。 輸出 每組測試數據輸N個正整數，其中，第i個數表示從S走到i號城市，必須要經過的上一個城市的編號。（其中i=S時，請輸出-1） 樣例輸入 1 10 1 1 9 1 8 8 10 10 3 8 6 1 2 10 4 9 5 3 7 樣例輸出 -1 1 10 10 9 8 3 1 1 8 一路深搜下去，如果碰到已有父節點，那麼該父節點不必替換，因為之前的父節點才是必經節點。 [cpp] #include <cstdio> #include <vector> #include <cstring> #define max 100000 + 2 using namespace std; vector<int> vec[max]; int pre[max]; void DFS(int s){ for(int i = 0; i != vec[s].size(); ++i){ if(pre[vec[s][i]]) continue; pre[vec[s][i]] = s; DFS(vec[s][i]); } } int main(){ int m, n, s, a, b; scanf("%d", &m); while(m--){ scanf("%d%d", &n, &s); for(int i = 1; i < n; ++i){ scanf("%d%d", &a, &b); vec[a].push_back(b); vec[b].push_back(a); } DFS(s); pre[s] = -1; for(int i = 1; i <= n; ++i) printf("%d ", pre[i]); printf("\n"); memset(vec, 0, sizeof(vec)); memset(pre, 0, sizeof(pre)); } return 0; }
