- 输入
- 第一行输入一个整数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
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define maxx 100005
vector<int>path[maxx];
int mark[maxx],result[maxx];
int main()
{
int cases,n,m,start,end,i;
scanf("%d",&cases);
while(cases--)
{
for(i=0;i<maxx;i++)
{
path[i].clear();
mark[i]=0;
result[i]=0;
}
scanf("%d%d",&n,&m);
for(i=0;i<n-1;i++)
{
//注意是无向图
scanf("%d%d",&start,&end);
path[start].push_back(end);
path[end].push_back(start);
}
queue<int>q;
q.push(m);
mark[m]=1;
result[m]=-1;
while(!q.empty())
{
int x=q.front();
q.pop();
int size=path[x].size();
for(i=0;i<size;i++)
{
if(!mark[path[x][i]])
{
q.push(path[x][i]);
mark[path[x][i]]=1;
result[path[x][i]]=x;
}
}
}
for(i=1;i<n;i++)
{
printf("%d ",result[i]);
}
printf("%d\n",result[n]);
}
return 0;
}
java ac代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;
class result
{
Vector<Integer>vector=new Vector<Integer>();
}
public class Main {
static result results[];
static int path[],start,citynumber;
static boolean mark[];
public static void bfs()
{
Queue<Integer>queue=new LinkedList<Integer>();
queue.add(start);
mark[start]=true;
while(!queue.isEmpty())
{
int s=queue.remove();
for(int i=0;i<results[s].vector.size();i++)
{
if(!mark[results[s].vector.get(i)])
{
path[results[s].vector.get(i)]=s;
mark[results[s].vector.get(i)]=true;
queue.add(results[s].vector.get(i));
}
}
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int cases=scanner.nextInt();
while(cases--!=0)
{
citynumber=scanner.nextInt();
start=scanner.nextInt();
results=new result[citynumber+4];
path=new int[citynumber+4];
mark=new boolean[citynumber+4];
Arrays.fill(mark, false);
Arrays.fill(path, -1);
for(int i=0;i<=citynumber;i++)
{
results[i]=new result();
}
for(int i=0;i<citynumber-1;i++)
{
int x,y;
x=scanner.nextInt();
y=scanner.nextInt();
results[x].vector.add(y);
results[y].vector.add(x);
}
bfs();
for(int i=1;i<=citynumber;i++)
{
System.out.print(path[i]+" ");
}
}
}
}