7-30 深入虎穴 (25分)（反向递归求路径 极简代码+思路和分析）

分析：这道题其实就是一道典型的搜索题，bfs和dfs应该都可以做，好像当成加权并查集也可以做，只不过并查集的话会有点麻烦。很多人可能上来就会从入口开始暴力往下搜，搜到底然后找出最远的。这是常规解法。
思路：首先定义两个数组，一个用来存储每个门到入口的距离，另一个用来存储这个门的上一个门是哪个门，这样就可以把所有门连起来（你可以在纸上画一下，会发现最后会构成一个跟树一样的东西）。然后我们很容易能够知道出口一定在输入k为0的门上（你细品）。这样我们可以在用一个动态数组来保存这些后面没有门的点，然后从后往前搜，这样就可以大大减少判断次数。详细代码如下：

#include
using namespace std;
const int maxn=100010,inf=0x3f3f3f3f;
int n,k,x,d[maxn],pre[maxn],maxi,maxs;
vector<int>v;
int getDepth(int i)
{if(d[i])	return d[i];if(i==1)	return 1;if(!i)		return inf;return d[i]=getDepth(pre[i])+1;
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>k;if(!k)	v.push_back(i);elsewhile(k--){cin>>x;pre[x]=i;}}for(int i=0;i<v.size();i++)if(getDepth(v[i])>maxs){maxs=getDepth(v[i]);maxi=v[i];}cout<<maxi;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！