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;
}


目录
相关文章
|
6月前
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(下)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
35 0
|
6月前
|
存储 人工智能
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(中)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
42 0
|
6月前
|
算法
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(上)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
82 0
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 机器人 C++
|
机器学习/深度学习 Java
【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索
每个数字有两种状态,删除或者未删除,因此可以使用状态压缩记录未删除的数字情况state,便于使用位运算进行状态的遍历及转移;使用状态压缩dp找到将所以数字删除的最大分数
101 0
【每日一题Day64】LC1799N 次操作后的最大分数和 | 状态压缩dp 状态压缩+dfs+记忆化搜索
|
算法
BFS——二分图判断
BFS——二分图判断
118 0
BFS——二分图判断
L3-008 喊山 (30 分)(bfs)
L3-008 喊山 (30 分)(bfs)
101 0
L3-008 喊山 (30 分)(bfs)
|
存储 算法 C语言
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
L2-026 小字辈 (25 分)(bfs)
L2-026 小字辈 (25 分)(bfs)
125 0