吝啬的國度 時間限制：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] ********************************* * 日期：2013-3-26 * 作者：SJF0115 * 題號: 題目20: 吝啬的國度 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=20 * 結果：AC * 來源：南陽理工OJ * 總結： **********************************/ #include<stdio.h> #include<iostream> #include<vector> #include<string.h> using namespace std; vector<int> G[100001]; int preCity[100001]; int vis[100001]; //深搜 void DFS(int location){ vis[location] = 1; //訪問與location相連的城市 for(int i = 0;i < G[location].size();i++){ int v = G[location][i]; if(!vis[v]){ //存儲訪問城市的上一站 preCity[v] = location; //printf("%d %d\n",location,v); DFS(v); } } } int main () { int N,M,City,Location,a,b,i,first; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); scanf("%d",&N); while (N--){ scanf("%d %d",&City,&Location); //初始化 for(i = 1;i <= City;i++){ G[i].clear(); } //輸入路徑 for(i = 1;i < City;i++){ scanf("%d %d",&a,&b); G[a].push_back(b); G[b].push_back(a); } //訪問城市 memset(vis,0,sizeof(vis)); vis[Location] = 1; preCity[Location] = -1; DFS(Location); //輸出訪問城市的上一站 first = 1; for(i = 1;i <= City;i++){ if(first){ first = 0; } else{ printf(" "); } printf("%d",preCity[i]); } printf("\n"); } return 0; } /********************************* * 日期：2013-3-26 * 作者：SJF0115 * 題號: 題目20: 吝啬的國度 * 來源：http://acm.nyist.net/JudgeOnline/problem.php?pid=20 * 結果：AC * 來源：南陽理工OJ * 總結： **********************************/ #include<stdio.h> #include<iostream> #include<vector> #include<string.h> using namespace std; vector<int> G[100001]; int preCity[100001]; int vis[100001]; //深搜 void DFS(int location){ vis[location] = 1; //訪問與location相連的城市 for(int i = 0;i < G[location].size();i++){ int v = G[location][i]; if(!vis[v]){ //存儲訪問城市的上一站 preCity[v] = location; //printf("%d %d\n",location,v); DFS(v); } } } int main () { int N,M,City,Location,a,b,i,first; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); scanf("%d",&N); while (N--){ scanf("%d %d",&City,&Location); //初始化 for(i = 1;i <= City;i++){ G[i].clear(); } //輸入路徑 for(i = 1;i < City;i++){ scanf("%d %d",&a,&b); G[a].push_back(b); G[b].push_back(a); } //訪問城市 memset(vis,0,sizeof(vis)); vis[Location] = 1; preCity[Location] = -1; DFS(Location); //輸出訪問城市的上一站 first = 1; for(i = 1;i <= City;i++){ if(first){ first = 0; } else{ printf(" "); } printf("%d",preCity[i]); } printf("\n"); } return 0; }
