题目
著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式：
输入首先在一行中给出正整数 N（<10^5 ），是门的数量。最后 N 行，第 i 行（1≤i≤N）按以下格式描述编号为 i 的那扇门背后能通向的门：
K D[1] D[2] ... D[K]
其中 K 是通道的数量，其后是每扇门的编号。
输出格式：
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。文章来源：https://www.toymoban.com/news/detail-764103.html
输入样例：
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.按照题目给的样例 整个迷宫应该是这样的
把门当成一个节点，道路当成边，测试用例应该是下面这样：
这就是一个有向无环图。也可以当成树来理解。
要找到离入口最远的一道门(结点)，那就是相当于找树的深度。
这里用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 深入虎穴(详细思路解释)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
