当前位置:网站首页>(multiple methods, need to continue to see) 7-11 go deep into the tiger's Den
(multiple methods, need to continue to see) 7-11 go deep into the tiger's Den
2022-07-06 16:44:00 【HBUcs2020】
Input :
The number of doors
Next N That's ok , The first i The line description number is i(1~N) The door behind the door that leads to :K D[1] D[2] ... D[K]
Output :
The number of the door farthest from the entrance
analysis :
Because the number of doors N<10 The fifth power of , So if you use an array, there will be segment errors
Because the problem of finding the farthest path , Think of depth first search , So use adjacency matrix ? Adjacency list ? Storage , Using the depth first traversal algorithm of adjacency matrix ? But how to find the length
Or use Dijkstra Algorithm this algorithm for calculating the shortest path is adapted to the longest path ?but This algorithm has not been remembered yet
There's another problem , What is the entrance , Do you want to use floyd Algorithm ,but alike , Didn't remember this algorithm
The result of thinking :
Problem solving should be divided into two steps :
1. Look for the entrance
2. Look for the furthest door , The longest path
that , How to find the entrance ? The title says “007 There are no two roads leading to the same door ” also " The title guarantees that such a result is the only ", therefore , There is only one entrance , And there is no way to this entrance , That is, you can only enter , Can not go out
Another question , How to find the longest path ? After intuitively feeling and thinking about knowledge , Recursive algorithms should be used 、
Last , What is used to store the data to ? Use c++ Of vector Container Bar , There will be no segment errors ,( Speaking of this , It seems that we should tidy up vector Knowledge points of advantages )c++ Arrangement of knowledge points :vector The advantages of _HBUcs2020 The blog of -CSDN Blog
Problem analysis completed , Here is Code :
It should be noted
1.dfs The iterator in is door1 Of
#include<iostream>
using namespace std;
#include<vector>
#include<cstring>
constexpr int MAXSIZE=100001;
vector<int> v[MAXSIZE];
int deep=0; // Maximum depth
int door; // Farthest gate
void DFS(int door1,int deep1)
{
//printf(" The door is %d Depth is %d\n",door,deep);
if(deep1>deep)
{
deep=deep1;
door=door1;
}
for(vector<int>::iterator it=v[door1].begin();it!=v[door1].end();it++)
DFS(*it,deep1+1);
}
int main()
{
bool vis[MAXSIZE]; // Is there a way to the door
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);
}
}
// entrance
int i;
for(i=1;i<=N;i++)
{
if(!vis[i])
break;
}
//cout<<" The furthest door "<<endl;
door=i; // entrance
DFS(i,1);
cout<<door<<endl;
return 0;
}
It seems that it is still used bfs Breadth first traversal and use queues to solve
The code is as follows , Come back when you have time
1. Using the queue
Be careful for(auto i:v[t]) Use ,
It seems that this idea is a little familiar , The use of the final queue is similar to a simple calculator .
subject :PTA | Program design experiment auxiliary teaching platform
#include <bits/stdc++.h> using namespace std; #define N 100005 vector<int> 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<int> 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<<res; }
2. Breadth first search
It seems to be the same method as the above queue
Not yet
#include<bits/stdc++.h> #define Maxsize 100001 using namespace std; int n; vector<int>v[Maxsize];/// Record form bool vis[Maxsize];/// Record whether the path leads to the current point int tt;/// Record the furthest door /// Breadth first traversal void BFS(int t){ queue<int>q; q.push(t); while(!q.empty()){ tt=q.front(); q.pop(); for(vector<int>::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;/// Proof point door i Can lead to the door d v[i].push_back(d); } } /// Look for the entrance int i; for(i=1;i<=n;i++){ if(!vis[i]) break; } /// Breadth first traverse the last node BFS(i); cout<<tt; return 0; }
边栏推荐
- Cmake Express
- Research Report on market supply and demand and strategy of China's four flat leadless (QFN) packaging industry
- 第三章 MapReduce框架原理
- Codeforces Global Round 19
- < li> dot style list style type
- LeetCode 1558. Get the minimum number of function calls of the target array
- Market trend report, technological innovation and market forecast of double door and multi door refrigerators in China
- Local visualization tools are connected to redis of Alibaba cloud CentOS server
- Detailed explanation of FLV format
- (lightoj - 1349) Aladdin and the optimal invitation (greed)
猜你喜欢
Chapter III principles of MapReduce framework
Hbuilder x format shortcut key settings
ByteDance new programmer's growth secret: those glittering treasures mentors
Business system compatible database oracle/postgresql (opengauss) /mysql Trivia
FLV格式详解
Chapter 5 detailed explanation of consumer groups
Mp4 format details
LeetCode 1584. Minimum cost of connecting all points
业务系统从Oracle迁移到openGauss数据库的简单记录
JS encapsulates the method of array inversion -- Feng Hao's blog
随机推荐
本地可视化工具连接阿里云centOS服务器的redis
Market trend report, technical innovation and market forecast of tabletop dishwashers in China
原生js实现全选和反选的功能 --冯浩的博客
音视频开发面试题
Codeforces Round #802(Div. 2)A~D
One hundred questions of image processing (11-20)
LeetCode1556. Thousand separated number
LeetCode 1545. Find the k-th bit in the nth binary string
Chapter III principles of MapReduce framework
Research Report of desktop clinical chemical analyzer industry - market status analysis and development prospect prediction
LeetCode 1020. Number of enclaves
使用jq实现全选 反选 和全不选-冯浩的博客
Spark独立集群Worker和Executor的概念
Cmake Express
LeetCode 1558. Get the minimum number of function calls of the target array
LeetCode 1550. There are three consecutive arrays of odd numbers
LeetCode 1638. Count the number of substrings with only one character difference
QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
7-4 harmonic average
字节跳动新程序员成长秘诀:那些闪闪发光的宝藏mentor们