团体程序设计天梯赛-练习集 L2-031 深入虎穴 (25分) dfs深搜+bfs广搜的两种思路

L2-031 深入虎穴 (25分)著名的王牌间谍 007 需要执行一次任务获取敌方的机密情报。已知情报藏在一个地下迷宫里迷宫只有一个入口里面有很多条通路每条路通向一扇门。每一扇门背后或者是一个房间或者又有很多条路同样是每条路通向一扇门…… 他的手里有一张表格是其他间谍帮他收集到的情报他们记下了每扇门的编号以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。内线告诉他情报就藏在迷宫的最深处。但是这个迷宫太大了他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。输入格式输入首先在一行中给出正整数 N10^​5是门的数量。最后 N 行第 i 行1 ≤ i ≤ N按以下格式描述编号为 i 的那扇门背后能通向的门K D[1] D[2] … D[K]其中 K 是通道的数量其后是每扇门的编号。输出格式在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。输入样例1332342561718190211101130011200输出样例12本题思路本题实际上就是求树高因此有深搜和广搜两种方式。需要特别注意本题没有告知入口在哪里因此需要找到入口即找到没有前驱节点的节点编号。dfs深搜#includeiostream#includealgorithm#includecstring#includecmath#includevectorconstintN100005;using namespace std;intn,k;intans,maxn-1,maxnode1;intvis[N],arr[N];vectorintvec[N];//关系树voiddfs(introot,intlen){vis[root]1;if(lenmaxn){maxnlen;maxnoderoot;}for(inti0;ivec[root].size();i){if(vis[vec[root][i]]0)dfs(vec[root][i],len1);}}intmain(){cinn;for(inti1;in;i){cink;while(k--){cinans;arr[ans];vec[i].push_back(ans);}}for(inti1;in;i){if(arr[i]0){dfs(i,1);break;}}coutmaxnodeendl;return0;}bfs广搜#includeiostream#includecstring#includealgorithm#includevector#includequeueconstintN100005;using namespace std;intn,k,root;vectorintvec[N];queueintqu;intarr[N],deep[N];voidbfs(introot){//返回inttemp;qu.push(root);deep[root]1;while(!qu.empty()){tempqu.front();qu.pop();for(inti0;ivec[temp].size();i){qu.push(vec[temp][i]);}}couttempendl;}intmain(){cinn;for(inti1;in;i){cink;while(k--){intans;cinans;arr[ans];vec[i].push_back(ans);}}for(inti1;in;i){//寻找入口if(arr[i]0){bfs(i);break;}}return0;}