時(shí)隔一年再做搜索題時(shí)遇到的第一題熏兄。
問題描述
在一個(gè)吝嗇的國度里有N個(gè)城市品洛，這N個(gè)城市間只有N-1條路把這個(gè)N個(gè)城市連接起來。現(xiàn)在摩桶，Tom在第S號城市桥状，他有張?jiān)搰貓D，他想知道如果自己要去參觀第T號城市硝清，必須經(jīng)過的前一個(gè)城市是幾號城市（假設(shè)你不走重復(fù)的路）辅斟。
輸入
第一行輸入一個(gè)整數(shù)M表示測試數(shù)據(jù)共有M(1<=M<=5)組
每組測試數(shù)據(jù)的第一行輸入一個(gè)正整數(shù)N(1<=N<=100000)和一個(gè)正整數(shù)S(1<=S<=100000)，N表示城市的總個(gè)數(shù)芦拿，S表示參觀者所在城市的編號
隨后的N-1行士飒，每行有兩個(gè)正整數(shù)a,b(1<=a,b<=N)查邢，表示第a號城市和第b號城市之間有一條路連通。
輸出
每組測試數(shù)據(jù)輸N個(gè)正整數(shù)变汪，其中侠坎，第i個(gè)數(shù)表示從S走到i號城市，必須要經(jīng)過的上一個(gè)城市的編號裙盾。（其中i=S時(shí)实胸，請輸出-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
分析
直接開數(shù)組 map[1000000][1000000]，可能會不過番官，用到了vector庐完，利用其不定長。
頭文件 #include<vector>
vector<int>a 就是一個(gè)不定長數(shù)組徘熔，類似于int a[]的整數(shù)數(shù)組门躯，只不過他的長度不確定，可以用a.size()讀取他的長度酷师。
vector<int>a[max] 就是一個(gè)二維數(shù)組讶凉，只是第一維的大小是固定的（不超過max），二維的大小就不固定了.
尾部插入數(shù)字：vec.push_back(a);
剛開始看了網(wǎng)上代碼也沒懂山孔，后來自己拿測試樣例走了一遍才明白懂讯。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int M,N,S;
vector<int>map[100005]; //記錄連通信息
int pre[100005]; //記錄每個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)
int a,b;
void dfs(int x){
for(int i=0; i<map[x].size(); i++){ //搜索所有與x相連的城市，即x的子節(jié)點(diǎn)
if(pre[map[x][i]]) //如果這個(gè)節(jié)點(diǎn)的pre已經(jīng)被賦值台颠，即已經(jīng)找到父親節(jié)點(diǎn)褐望，就跳過，去找x的下一個(gè)子節(jié)點(diǎn)串前。
continue;
else{ //還沒賦值瘫里，即還沒找到父親節(jié)點(diǎn)
pre[map[x][i]] = x; //x就是這個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)，因?yàn)槭前凑諛涞捻樞蛞来梧l(xiāng)下搜索的
dfs(map[x][i]); //在我找個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)
}
}
}
int main()
{
scanf("%d",&M);
while(M--){
memset(map, 0, sizeof(map));
memset(pre, 0, sizeof(pre));
scanf("%d%d",&N,&S);
for(int i=0; i<N-1; i++){
scanf("%d%d",&a, &b);
map[a].push_back(b); //在 a 的連通城市中加上 b
map[b].push_back(a); //在 b 的連通城市中加上 a
}
pre[S] = -1; //當(dāng)前的起始城市沒有父親節(jié)點(diǎn)（因?yàn)槭且运麨樽钌戏礁?jié)點(diǎn)構(gòu)造樹的）
dfs(S); //從當(dāng)前城市開始搜索荡碾，為每個(gè)節(jié)點(diǎn)尋找父親節(jié)點(diǎn)
for(int i=1; i<=N; i++) //打印每個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)谨读，即從 S 到每個(gè)城市畢竟的上一個(gè)城市
cout<<pre[i]<<" ";
}
return 0;
}
