L2-031 深入虎穴 (25分)

摘要:
著名的特朗普间谍007需要执行一项任务,从敌人那里获取机密信息。已知信息隐藏在地下迷宫中,迷宫只有一个入口。迷宫里有许多通道,每条通道通向一扇门。他手里有一张桌子,是其他间谍为他收集的信息。他们记录了每个门的编号以及门后每个通道到达的门的编号。007发现没有两条路通向同一扇门。知情者告诉他,这些信息隐藏在迷宫的最深处。标题保证此类结果是唯一的。

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:

输入首先在一行中给出正整数 N(<),是门的数量。最后 N 行,第 i 行(1)按以下格式描述编号为 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

给出了一棵树的结点之间的关系,要求找最深的叶子结点。

代码:
#include <iostream>
#include <cstdio>
#define MAX 100005
using namespace std;
int n,m,t;
int f[MAX],val[MAX];
void get(int k) {
    if(f[k] == 0) {
        val[k] = 1;
        return;
    }
    if(val[f[k]] == 0) get(f[k]);
    val[k] = val[f[k]] + 1;
}
int main() {
    int k,d;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&k);
        for(int j = 0;j < k;j ++) {
            scanf("%d",&d);
            f[d] = i;
        }
    }
    for(int i = 1;i <= n;i ++) {
        get(i);
        if(m < val[i]) m = val[i],t = i;
    }
    printf("%d",t);
    return 0;
}

免责声明:文章转载自《L2-031 深入虎穴 (25分)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Google Adsense(Google网站联盟)广告申请指南Mapx自带的工具的理解下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

Matlab高级教程_第二篇:Matlab相见恨晚的模块_02_并行运算-1

3 MATLAB2009之后,并行计算工具箱和并行计算服务退出。通过PCT和DCS,用户可以实现基于多核平台、多处理器平台和集群平台的多个并行计算任务。除了支持上述通用功能外,PCT还增加了对GPU单元的支持。现在来看彼此已经太晚了:用parfor并行化for循环。在编程中,使计算量最小化的代码总是一个循环。7 parpool命令在不启动并行池的情况下配置并...

vSphere HA 原理与配置

应当基于可用性需求和群集的特性选择vSphereHA接入控制策略。...

Spring Boot 核心配置文件 bootstrap &amp;amp; application

boostrap由父ApplicationContext加载,比applicaton优先加载boostrap里面的属性不能被覆盖3、bootstrap/application的应用场景application配置文件这个容易理解,主要用于SpringBoot项目的自动化配置。这个父级的SpringApplicationContext是先加载的,在加载appli...

RPi 树莓派 DSI 接口研究 MIPI raspberry pi

我已经玩树莓派很久了。我发现尚未使用DSI显示界面。经过一些研究,我发现它很有趣。我稍后会记录相关信息。(更新1:目前,整个网络上有很多方案来研究hdmi和mipi之间的相互转换方案:a.)mipi屏幕+hdmi界面:大多数都是因为有很多mipi屏幕和漂亮的参数而被研究的。详细信息:谷歌,得益于包括智汇在内的各种大神的研发,如Pocket LCD方案。最困难...

内网esxi磁盘空间不足导致虚拟机宕机

因为一些占用太多空间的虚拟机可能无法启动。我不断拍摄快照以保存测试版本。我跳过了同一网段上的一个虚拟机ssh,并一直看着翻译器学习如何释放虚拟磁盘空间。您只能创建一个新的虚拟机来读取原始磁盘目录,并且只能重新构建一个新Linux机器进行测试。然后上传一个测试文件(最大程度地模拟其他虚拟机环境)。首先,你需要关闭机器。厚配置延迟将整个虚拟机目录文件清零,如下所...

PX4 飞控源码系统框架介绍

该部分主要是PX4系统的使用的所有的数据结构的集合部分,各种任务和sensor驱动中需要获取的sensor数据都在此部分,还包含各种运行状态的数据结构。...