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