zzulioj--1711--漂洋过海来看你(dfs+vector)
2024-10-01 13:20:22
1711: 漂洋过海来看你
Time Limit: 1 Sec Memory Limit:
128 MB
Submit: 89 Solved: 33
SubmitStatusWeb
Board
Description
BMan和hyx住在一个神奇的国度,这个国度有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。 现在BMan在第S号城市,他经常想起那个一起AC过的队友hyx,记忆它总是慢慢的累积,在他心中无法抹去,可是他并不知道hyx 在哪个城市,所以他决定用尽半年的积蓄漂洋过海去找hyx,现在BMan很想知道如果他想去hyx所在的第X号城市,必须经过的前
一个城市是第几号城市(放心,由于心系队友,BMan是不会选择走重复的路的~)
Input
第一行输入一个整数T表示测试数据共有T(1<=T<=10)组 每组测试数据的第一行输入一个正整数N(1<=N<=1000)和一个正整数S(1<=S<=1000),N表示城市的总数,S是BMan所在城市的编号 随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。
Output
每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号(其中i=S时,请输出-1)
Sample Input
110 11 91 88 1010 38 61 210 49 53 7
Sample Output
-1 1 10 10 9 8 3 1 1 8
HINT
Source
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
int b[1010];
vector<int>g[1010];
void dfs(int x)
{
for(int i=0;i<g[x].size();i++)
{
if(b[g[x][i]]) continue;
b[g[x][i]]=x;
dfs(g[x][i]);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,s,x,y;
scanf("%d%d",&n,&s);
memset(b,0,sizeof(b));
for(int i=1;i<n;i++)
g[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
b[s]=-1;
dfs(s);
for(int i=1;i<=n;i++)
{
if(i>1)
printf(" ");
printf("%d",b[i]);
}
printf("\n");
}
return 0;
}
最新文章
- JAVASE02-Unit09: 多线程基础
- android开发中难免遇到listview刷新数据出现异常
- openlayer3 获取feature
- 《JavaScript高级程序设计》读书笔记--(3)引用类型
- 不同版本jq冲突问题
- K910 升级Android 4.4.2可用的Google Service Framework
- 微信C# SDK
- OpenJudge计算概论-排队游戏【这个用到了栈的思想】
- [物理学与PDEs]第5章习题参考解答
- 【转】Android学习系列(1)--为App签名(为apk签名)
- (转)基于PHP的cURL快速入门
- yacc和lex在ubuntu上安装
- mac使用小技
- SpringCloud高可用Eureka搭建
- IPFS开发团队是如何工作的?
- Web前端 页面功能——点击按钮返回顶部的实现方法
- LabVIEW版本控制(转)
- pageHelper多个sql分页
- as3:sprite作为容器使用时,最好不要指定width,height
- django MTV架构下的网站开发步骤