下列软件属于网站开发工具的是,个人购物网站建设,合肥室内设计工作室,兰州app开发L2-3深入虎穴
分数 25
名的王牌间谍 007 需要执行一次任务#xff0c;获取敌方的机密情报。已知情报藏在一个地下迷宫里#xff0c;迷宫只有一个入口#xff0c;里面有很多条通路#xff0c;每条路通向一扇门。每一扇门背后或者是一个房间#xff0c;或者又有很多条路获取敌方的机密情报。已知情报藏在一个地下迷宫里迷宫只有一个入口里面有很多条通路每条路通向一扇门。每一扇门背后或者是一个房间或者又有很多条路同样是每条路通向一扇门…… 他的手里有一张表格是其他间谍帮他收集到的情报他们记下了每扇门的编号以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他情报就藏在迷宫的最深处。但是这个迷宫太大了他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式
输入首先在一行中给出正整数 N105是门的数量。最后 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 题解
根据每个点的入度来判断起点入度为0的点就是起点。从起点开始bfs每步记录长度。
#includebits/stdc.h
using namespace std;
#define ll long long
#define endl \n
int n;
vectorint g[100005];
int deg[100005];
mapint,int mp;
int root;
int v[100005];
int ans;
int main()
{cinn;for(int i1;in;i){int k;cink;for(int j1;jk;j){int x;cinx;g[i].push_back(x);deg[x];//入度加一}}for(int i1;in;i){if(deg[i]0){rooti;break;}}mp[root]0;queueint q;q.push(root);while(!q.empty()){int tq.front();q.pop();for(int i0;ig[t].size();i){q.push(g[t][i]);mp[g[t][i]]mp[t]1;}}for(auto k:mp){ansmax(ans,k.second);//寻找最长长度}for(auto k:mp){if(k.secondans){coutk.firstendl;break;}}return 0;}
