nyoj20——有向无环图深搜模板
2024-08-29 18:59:18
吝啬的国度
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
- 在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。
- 输入
- 第一行输入一个整数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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+; int pre[maxn];
vector<int>v[maxn]; void dfs(int x)
{
for(int i=;i < v[x].size();i++){
if(pre[v[x][i]] == ){ //表示与x相连的节点未被遍历过
pre[v[x][i]] = x;
dfs(v[x][i]);
}
}
} int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(pre,, sizeof(pre));
memset(v,, sizeof(v));
int n,s;
scanf("%d%d",&n,&s);
pre[s] = -;
for(int i=;i < n-;i++){
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(s);
for(int i=;i <= n;i++){
printf("%d ",pre[i]);
}
}
return ;
}一开始我不是很理解题意,什么叫“必须要经过的上一个城市的编号”,看了别人的代码更加迷惑。
后来看到是输入 n-1 组关系数据,瞬间明白了,是有向无环图,所以说不会出现有多条路径到达同一点的情况。
最新文章
- Failed to execute goal org.apache.maven.plugins:maven-antrun-plugin:1.7:run (dist) on project hadoop-kms: An Ant BuildException has occured
- IOS 7 风格Checkbox
- capwap DTSL 加密分析
- OSG绘制几何图形
- 剖析MapReduce 作业运行机制
- EJB3Persistence开发手册-原生SQL查询(NativeSQL)
- linux 压缩/解压命令大全
- lua中的面向对象编程
- O(nlogn)算法,最长上升子序列,,非动规
- C# 错误:空对象不能转换为值类型
- 【学习笔记】tensorflow图片读取
- Ubuntu14.04+ROS 启动本地摄像头
- 使用@Autowird注入报空指针异常
- Leetcode(三)无重复字符的最长子串
- RabbitMQ实战经验分享
- TestLink测试管理工具的使用举例—第一篇
- python -django 之第三方支付
- 258. Add Digits 入学考试:数位相加
- 发布Asp.net core到nginx 使用nginx代理
- [ssh]如何设计ARM板上多用户key登录系统
热门文章
- delphi程序中定义热键
- C语言赋初始值
- HDU 1116 Play on Words(欧拉路径(回路))
- java的接口为什么不能实例化
- $Linux vi/vim编辑器常用命令与用法总结 (Markdown编辑版)
- laravel 图片上传 ajax 方式
- AVAudioSession(3):定制 Audio Session 的 Category
- React组件绑定this的四种方式
- Web安全学习笔记之Kali部署DVWA和OWASPBWA
- JS等比例缩放图片,限定最大宽度和最大高度