【题目链接:NYOJ-20】
很巧妙,要好好想想
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int>a[];
int b[],n,s;
void dfs(int x,int y){
for (int i = ; i <a[x].size();i++)
if (a[x][i] != y)
dfs(a[x][i],b[a[x][i]]=x);
return;
}
int main(){
int M,x,y;
scanf("%d",&M);
while (M--){
scanf("%d%d",&n,&s);
for (int i = ; i <n; i++){
a[i].clear();
}
for (int i = ; i <n; i++){
scanf("%d%d",&x,&y);
a[x].push_back(y); //相当二维数组
a[y].push_back(x);
}
b[s] = -;//与S相等则为-1
dfs(s,-);
for (int i = ; i <= n; i++)
printf("%d ",b[i]);
printf("\n");
}
return ;
}