首页 > 代码库 > nyist 20 吝啬的国度（dfs）
nyist 20 吝啬的国度（dfs）
吝啬的国度
- 题目描述：
- 在一个吝啬的国度里有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
- 题目大意：
- n个城市，n-1条无向边，问从s城市到其他城市的前一个城市的编号。
- 解题思路：
- 利用深度优先搜索，从s点开始搜起。节点个数的数据过大所以不能用邻接矩阵存边
- 我这里用的容器（vector）模拟邻接表的存储。
- AC代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <vector> 5 6 using namespace std; 7 8 int f[100010]; // 记录到达每个城市的前一个城市的节点 9 vector< int> vec[100010]; // 用容器模拟邻接表存储边的信息10 void dfs(int x)11 {12 int len = vec[x].size(); // 计算出和x城市相连的城市个数13 for (int i = 0; i < len; i ++)14 {15 if (f[vec[x][i]]) // 不走重复的路16 continue;17 f[vec[x][i]] = x;18 dfs(vec[x][i]);19 }20 }21 int main ()22 {23 int t,n,s,i,j,a,b;24 scanf("%d",&t);25 while (t --)26 {27 memset(f,0,sizeof(f));28 memset(vec,0,sizeof(vec));29 scanf("%d%d",&n,&s);30 for (i = 0; i < n-1; i ++)31 {32 scanf("%d%d",&a,&b); // 无向边33 vec[a].push_back(b);34 vec[b].push_back(a);35 }36 f[s] = -1; dfs(s);37 printf("%d",f[1]);38 for (i = 2; i <= n; i ++)39 printf(" %d",f[i]);40 printf("\n");41 }42 return 0;43 }
nyist 20 吝啬的国度（dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。