链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=20
邻接表+BFS
#include <iostream>
#include <vector>
#include <queue>
#define MAX_N 100000
using namespace std;
int M;
typedef pair<int ,int> P; // 节点编号，距离
vector<P> G[MAX_N+5];
bool vis[MAX_N+5]; //访问标记
int pos[MAX_N+5]; //顺序
int N,S;
void init()
{
for(int i=0;i<MAX_N+5;i++)
{
vis[i]=false;
pos[i]=0;
G[i].clear();
}
vis[S]=true;
}
void bfs()
{
queue<P> que;
que.push(make_pair(S,0)); //压入起点
while(que.size())
{
P p=que.front();que.pop();
int d=p.second,v=p.first;
for(unsigned int i=0;i<G[v].size();i++) //向连通的村庄扩散
{
int vt=G[v].at(i).first;
if(vis[vt]==false) //无环图，防止重复
{
G[v].at(i).second=d+1; //距离+1
vis[vt]=true; //已访问过
que.push(G[v].at(i));
pos[vt]=max(pos[vt],d+1);
}
}
}
}
void solve()
{
cin>>M;
int a,b;
while(M--)
{
cin>>N>>S;
init();
for(int i=0;i<N-1;i++)
{
cin>>a>>b;
G[a].push_back(make_pair(b,0)); //无向图
G[b].push_back(make_pair(a,0));
}
bfs();
for(int i=1;i<=N;i++)
{
if(S==i)
{
cout<<"-1 ";
continue;
}
for(unsigned int j=0;j<G[i].size();j++)
{
int vt=G[i].at(j).first;
if(pos[vt]==pos[i]-1)
cout<<vt<<" ";
}
}
cout<<endl;
}
}
int main()
{
solve();
return 0;
}