(multiple methods, need to continue to see) 7-11 go deep into the tiger's Den

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;
}