NYOJ 题目20吝啬的国度(DFS)

2024-06-03 19:48
文章标签 题目 dfs 20 nyoj 国度 吝啬

本文主要是介绍NYOJ 题目20吝啬的国度(DFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

吝啬的国度

时间限制: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

首先想到的是使用邻接矩阵(菜鸟!没办法o(╯□╰)o), 差不多快写完了,然后看题目中N的范围,100000,开一个二维数组city[N][N],根本没办法编译,==!于是放弃邻接矩阵,改用邻接表存储,我把代码那个写啊。。。。指针,结构体,头结点什么的一会儿就晕了, 后来看到有人使用STL中的 vector ,可以用来代替二维数组,不过差不多,于是我就试着用vector (第一次用也不知道理解的对不对,,以前见过没用), vector <int> city[N];  相当于N个vector,跟二维数组差不多

 

代码:

 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 100005
using namespace std;
vector <int> city[N];
int p[N];
bool vis[N];
void DFS(int x)
{
vis[x] = 1;
int i=0,len;
len = city[x].size();
for(i=0;i<len;i++)
{
if(!vis[city[x][i]])
{
p[city[x][i]]=x;
DFS(city[x][i]);
}
//	i++;
}
}
int main()
{
int m,n,s,i,x,y;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&n,&s);
for(i=0;i<=n;i++) city[i].clear();//这里初始化清空,第一次没写WA了
for(i=0;i<n-1;i++)
{
scanf("%d%d",&x,&y);
city[x].push_back(y);
city[y].push_back(x);
}
memset(vis,0,sizeof(vis));
p[s]=-1;
DFS(s);
for(i=1;i<n;i++) printf("%d ",p[i]); printf("%d\n",p[n]);
}
return 0;
}


 

别人优秀代码,用的map,还没用过,改天研究研究!

 
#include <stdio.h>
#include <memory.h>
int map[100005];
void Adjust(int currentCity)
{
int priorCity = map[currentCity];
if (priorCity != 0)
{
Adjust(priorCity);
map[priorCity] = currentCity;
}
}
int main()
{
int i, testNum, cityNum, startCity, cityA, cityB;
scanf("%d", &testNum);
while (testNum-- != 0)
{
scanf("%d%d", &cityNum, &startCity);
memset(map, 0, sizeof(int)*cityNum + 1);
for (i = 1; i < cityNum; i++)
{
scanf("%d%d", &cityA, &cityB);
if (map[cityB] == 0)
{
map[cityB] = cityA;
}
else
{
Adjust(cityA);
map[cityA] = cityB;
}
}
Adjust(startCity);
map[startCity] = - 1;
for (i = 1; i < cityNum; i++)
{
printf("%d ", map[i]);
}
printf("%d\n", map[i]);
}
return 0;
}        


 

 

 

 

 

 

 

 

 

 

 

 

 

 

这篇关于NYOJ 题目20吝啬的国度(DFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1027939

相关文章

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访