（多种方法，需要继续看）7-11 深入虎穴
输入：
门的数量
接下来N行，第i行描述编号为i（1~N）的门背后能通向的门:K D[1] D[2] ... D[K]
输出：
距离入口最远的门的编号
分析：
因为门的数量N<10的五次方，所以如果使用数组一定会出现段错误
因为求最远路径问题，想到深度优先搜索，所以使用邻接矩阵？邻接表？存储，用邻接矩阵的深度优先遍历算法？但是怎么求长度呢
还是使用Dijkstra算法这个算最短路径的算法改编为最长路径？but这个算法到现在也没记住
还有一个问题，入口是什么，难道要使用floyd算法吗，but同样的，没记住这个算法
思考结果：
问题解决应该分为两步：
1.寻找入口
2.寻找最远的那扇门，即最长路径
那么，如何寻找入口？题目说“007发现不存在两条路通向同一扇门”并且"题目保证这样的结果是唯一的",所以，入口有且只有一个，并且没有道路可以通向这个入口，即只能进，不能出
另一个问题，如何寻找最长路径呢？直观感觉并且思考会的知识之后，应该使用递归算法、
最后，使用什么存储通向的数据呢？使用c++的vector容器吧，不会出现段错误，（说到这里，似乎应该整理一下vector优势的知识点啦）c++知识点整理：vector的优势_HBUcs2020的博客-CSDN博客
问题分析完成，下面是代码：
应该注意
1.dfs中的迭代器为door1的
#include
using namespace std;
#include
#include
constexpr int MAXSIZE=100001;
vector v[MAXSIZE];int deep=0; //最大深度
int door; //最远门void DFS(int door1,int deep1)
{//printf("门为%d 深度为%d\n",door,deep);if(deep1>deep){deep=deep1;door=door1;}for(vector::iterator it=v[door1].begin();it!=v[door1].end();it++)DFS(*it,deep1+1);
}
int main()
{bool vis[MAXSIZE]; //是否有通向该门的道路memset(vis,false,sizeof(vis));int N;cin>>N;for(int i=1;i<=N;i++){int k;cin>>k;while(k--){int n;cin>>n;vis[n]=true;v[i].push_back(n);}}//入口int i;for(i=1;i<=N;i++){if(!vis[i])break;}//cout<<"最远的门"< 好像还有使用bfs广度优先遍历和使用队列来解决的
代码如下，有时间再来看
1.使用队列
注意for(auto i:v[t])的使用，
好像这个思路有些许的熟悉，最后队列的使用方法类似简单计算器。
题目：PTA | 程序设计类实验辅助教学平台
#includeusing namespace std; #define N 100005 vector v[N]; bool visit[N]={false}; int main() {int n,k,t;cin>>n;for(int i=1; i<=n; i++){cin>>k;while(k--){cin>>t;visit[t]=true;v[i].push_back(t);}}int start,res=1;for(start=1; start<=n; start++)if(!visit[start])break;queue q;q.push(start);while(!q.empty()){t=q.front();for(auto i:v[t])q.push(i);q.pop();if(q.size()==1)res=q.front();}cout<
2.广度优先搜索
好像跟上面的队列是同一种方法
还没有看
#include#define Maxsize 100001 using namespace std; int n; vector v[Maxsize];///记录表格 bool vis[Maxsize];///记录是否路径通向当前点 int tt;///记录最远的那扇门 ///广度优先遍历 void BFS(int t){queue q;q.push(t);while(!q.empty()){tt=q.front();q.pop();for(vector ::iterator it=v[tt].begin();it!=v[tt].end();it++)q.push(*it);} } int main(){memset(vis,false,sizeof(vis));cin>>n;for(int i=1;i<=n;i++){int m;cin>>m;while(m--){int d;cin>>d;vis[d]=true;///证明点门i能通向门dv[i].push_back(d);}}///寻找入口int i;for(i=1;i<=n;i++){if(!vis[i])break;}///广度优先遍历最后一个结点BFS(i);cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！