PTA 深入虎穴(详细思路解释)

这篇具有很好参考价值的文章主要介绍了PTA 深入虎穴(详细思路解释)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:
输入首先在一行中给出正整数 N(<10^5 ),是门的数量。最后 N 行,第 i 行(1≤i≤N)按以下格式描述编号为 i 的那扇门背后能通向的门:

K D[1] D[2] ... D[K]

其中 K 是通道的数量,其后是每扇门的编号。
输出格式:
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例:
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0
输出样例:
12

##思路
1.按照题目给的样例 整个迷宫应该是这样的
把门当成一个节点,道路当成边,测试用例应该是下面这样:
pta深入虎穴,算法,深度优先遍历
这就是一个有向无环图。也可以当成树来理解。
要找到离入口最远的一道门(结点),那就是相当于找树的深度。
这里用BFS来求解,思路很简单,相当于是树的层序遍历。
2.注意:入口不是固定的,这是题目的隐含条件。如何找到入口呢?就是没有边指向的那个节点,也就是入度为0的节点,没有节点指向它。
##代码及详细注释文章来源地址https://www.toymoban.com/news/detail-764103.html

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//节点 
struct node{
	int num;//节点的编号
	int pre;//前驱节点编号
	vector<int> next;//后继节点集合 
};

int main()
{
	int k;scanf("%d",&k);
	node nodes[k+1];//K个节点 
	int roots[k+1]={0};//这个数组用来找到根节点 
	int root;//根节点 
	for (int i=1;i<=k;i++){
		int t;scanf("%d",&t);
		nodes[i].num=i;
		for (int j=0;j<t;j++){
			int tt;scanf("%d",&tt);
			nodes[i].next.push_back(tt);
			nodes[tt].pre=i;//找到节点的前驱节点 
			roots[tt]++;//tt这个节点有入度 记录下来 
		}
	}
	//找到根节点
	for (int i=1;i<=k;i++) {
		if (roots[i]==0)root=i;//因为根节点入度为0 
	}
	int path[k+1]={0};//path[i]代表第i个节点到root的长度 
	path[root]=0;
	//树的层次遍历 老套路题啦~ 
	queue<int>q;
	q.push(root);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		if (t!=root)path[t]=path[nodes[t].pre]+1;
		for (int i=0;i<nodes[t].next.size();i++){
			q.push(nodes[t].next[i]);
		}
	}
	int v=0,index=root;
	//找到离root最远的那道门 
	for (int i=1;i<=k;i++){
		if (path[i]>v){
			v=path[i];index=i;
		}
	}
	cout<<index;
}
```
##结果
pta深入虎穴,算法,深度优先遍历
有问题的小伙伴可以在评论区留言吼~我看到了会回复的^ ~ ^

到了这里,关于PTA 深入虎穴(详细思路解释)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剪切粘贴(pta团体天梯题)c++超简单详细刨析版

    使用计算机进行文本编辑时常见的功能是剪切功能(快捷键:Ctrl + X)。请实现一个简单的具有剪切和粘贴功能的文本编辑工具。 工具需要完成一系列剪切后粘贴的操作,每次操作分为两步: 剪切:给定需操作的起始位置和结束位置,将当前字符串中起始位置到结束位置部分

    2024年03月12日
    浏览(20)
  • C语言 switch语句详细讲解 简单计算器及PTA例题季节判断,今天星期几-1(switch语句实现), 数据按需处理

    (1) 当被测试的变量等于 case 中的常量时,case 后跟的语句将被执行,直到遇到  break  语句为止。 (2)不是每一个 case 都需要包含  break 。如果 case 语句不包含  break ,控制流将会  继续  后续的 case,直到遇到 break 为止。 (3) 上面所有 case 都无法判断结果时,可用 default 代替

    2024年02月05日
    浏览(25)
  • PTA 动态规划

       文章目录 一、函数题 二、编程题 长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1=ij=n。试设计一个算法,计算出从游艇出租站1 到游

    2024年02月03日
    浏览(13)
  • PTA:猜数字-交互版

    你需要编写一个“猜数字”的程序。跟你做过的大部分题目不一样,你需要通过不断地询问另外一个程序(以下称之为“交互程序”)来猜到最终的数字。 在你的程序刚运行时,交互程序会通过标准输入给你提供一个数字 N,表示你需要猜的数字在 1 到 N 范围里。 接下来

    2024年02月02日
    浏览(13)
  • PTA-7-4 堆排序

    代码如下:

    2024年01月15日
    浏览(22)
  • 【PTA】

    (!!!) L1-002 打印沙漏 (20 分) L1-003 个位数统计 (15 分) L1-005 考试座位号 (15 分) (!!!) L1-006 连续因子 (20 分) L1-008 求整数段和 (10 分) (!!!) L1-009 N个数求和 (20 分) L1-011 A-B (20 分) L1-015 跟奥巴马一起画方块 (15 分) L1-016 查验身份证 (15 分) L1-017 到底有多二 (15 分) L1-018 大笨钟 (10 分) L1-0

    2024年02月07日
    浏览(48)
  • 奇偶分家 PTA

    题目: 给定 N 个正整数,请统计奇数和偶数各有多少个? 输入格式: 输入第一行给出一个正整 N (≤1000);第2行给出 N 个非负整数,以空格分隔。 输出格式: 在一行中先后输出奇数的个数、偶数的个数。中间以1个空格分隔。 输入样例: 输出样例: 代码实现 : 注释:

    2024年01月18日
    浏览(46)
  • PTA | Wifi密码

    下面是微博上流传的一张照片:“各位亲爱的同学们,鉴于大家有时需要使用 wifi,又怕耽误亲们的学习,现将 wifi 密码设置为下列数学题答案:A-1;B-2;C-3;D-4;请同学们自己作答,每两日一换。谢谢合作!!~”—— 老师们为了促进学生学习也是拼了…… 本题就要求你写

    2024年02月19日
    浏览(8)
  • python pta实验八

    ​​​​​​​ 目录 一、判断题 二、选择题 二、函数题fn 6-1 判断回文函数 6-2 计算一元二次方程的根 三、编程 7-1 计算球体积 7-2 计算每月电费费用 7-3 按顺序输出小于指定值的所有斐波纳契数  7-4 句子首字母变大写 7-5 计算每个学生的平均成绩 在Python中使用浮点数除法运

    2024年02月06日
    浏览(12)
  • PTA三次作业

    1.前言: 第一次作业难度较大,从无到有的设计,涉及到的主要类有Paper,Question,AnswerPaper,Main,主要题目方向为字符串判断与字符串处理(提取有效信息),判断对错算总分,配合一些Java自带的数据结构如ArrayList即可快速解决问题,第一次作业是后面作业的基础,需自行了解

    2024年04月22日
    浏览(17)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包