首页 > 代码库 > NYOJ20 吝啬的国度 (dfs)
NYOJ20 吝啬的国度 (dfs)
题目描述:
http://acm.nyist.net/JudgeOnline/problem.php?pid=20
- 在一个吝啬的国度里有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
题目分析:
不要一位此题只是简单的单联通问题,此题是个深度搜索问题,正常的搜索问题,可能是题目没有描述清楚,本题代码参考的大神的代码。。。
AC代码:
/** *dfs,深度搜索, *注意找到最好的路线,从A能到b,那么从b必然也能到a */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cstring> #include<cmath> using namespace std; int map_vis[100005]; void a_prior_dfs(int a){ int p=map_vis[a]; if(p!=0){//继续向前搜素 a_prior_dfs(p); map_vis[p]=a;//反向标记 } } int main() { int t,n,s; scanf("%d",&t); while(t--){ memset(map_vis,0,sizeof(map_vis)); scanf("%d%d",&n,&s); int a,b; for(int i=0;i<n-1;i++){ scanf("%d%d",&a,&b); if(map_vis[b]==0) map_vis[b]=a; else{ a_prior_dfs(a); map_vis[a]=b;//反向标记 } } a_prior_dfs(s);//从出发点继续搜索 map_vis[s]=-1; for(int i=1;i<=n;i++){ printf("%d ",map_vis[i]); } printf("\n"); } return 0; }
NYOJ20 吝啬的国度 (dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。