L2-031 深入虎穴 (25 分)(bfs)

简介: L2-031 深入虎穴 (25 分)(bfs)

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


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


输入格式:

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

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

其中 K 是通道的数量,其后是每扇门的编号。


输出格式:

在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。


输入样例:

1. 13
2. 3 2 3 4
3. 2 5 6
4. 1 7
5. 1 8
6. 1 9
7. 0
8. 2 11 10
9. 1 13
10. 0
11. 0
12. 1 12
13. 0
14. 0


输出样例:

12


思路:用一个动态二维数组来存储关系,然后用bfs一层一层往下遍历到最后一个数就是距离入口最远的那扇门的编号

26c936a6d9ef42a6ae7831fc94f8c4ad.jpg


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>v[N];//二维数组
int vis[N];//标记
int bfs(int u)
{
    queue<int> q;
    int x;
    q.push(u);
    while(!q.empty())
    {
        x=q.front();
        vis[x]=1;
        q.pop();
        for(int i=0;i<v[x].size();i++)
            if(!vis[v[x][i]])
                q.push(v[x][i]);
    }
    return x;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k,x;
        cin>>k;
        while(k--)
        {
            cin>>x;
            vis[x]=1;
            v[i].push_back(x);
        }
    }
    int root;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            root=i;//找到根节点
            break;
        }
    }
    memset(vis,0,sizeof(vis));
    cout<<bfs(root);
    return 0;
}


目录
相关文章
|
机器学习/深度学习 存储 算法
【DFS经典例题】2n皇后问题
【DFS经典例题】2n皇后问题
76 0
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
78 0
|
算法
BFS——二分图判断
BFS——二分图判断
120 0
BFS——二分图判断
L3-008 喊山 (30 分)(bfs)
L3-008 喊山 (30 分)(bfs)
102 0
L3-008 喊山 (30 分)(bfs)
|
存储 算法 C语言
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
|
算法 Java 索引
【算法题解】 Day10 BFS | DFS
今天的算法是 「BFS | DFS」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”
102 0
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
107 0
L2-026 小字辈 (25 分)(bfs)
L2-026 小字辈 (25 分)(bfs)
127 0
|
算法 C++ Python
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索