L2-031 go deep into the tiger's den (25 points)

This time, the questions are 2021 Nian TIANTI

L2-031 Deep into the tiger's lair (25 branch )

Famous trump spy 007 Need to perform a task , Get confidential information from the enemy . The known information is hidden in an underground labyrinth , There is only one entrance to the maze , There are many ways in it , Each road leads to a door . Behind every door or in a room , Or there are many ways , It's the same way that every road leads to a door …… He has a form in his hand , It's the intelligence that other spies collected for him , They wrote down the number of each door , And the number of the door that each access road behind the door reaches .007 There are no two roads leading to the same door .

The insiders told him , Intelligence is hidden in the deepest part of the maze . But this maze is too big , He needs your help —— Please program to help him find the door farthest from the entrance .

Input format ：

Input first gives a positive integer on a line N（<105）, It's the number of doors . Last N That's ok , The first i That's ok （1≤i≤N） Describe the number as... In the following format i The door that can lead to behind the door of ：

K D[1] D[2] ... D[K]

among K It's the number of channels , Followed by the number of each door .

Output format ：

Output the number of the door farthest from the entrance in one line . The title guarantees that such a result is the only .

sample input ：

13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0

sample output ：

12

Answer key

Find your code more beautiful than before
Writing is more fluent
It is indeed a great improvement over last year's ladder
come on. Chongwen

Code

BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int n = 1e5 + 10;
int dp[n];
vector<int> v[n];

void bfs(int i)
{
    
    queue<int> q;
    q.push(i);
    int ans = 1;
    while (!q.empty())
    {
    
        auto x = q.front();
        q.pop();
        ans = x;
        for(auto &e : v[x])
            q.push(e);

    }
    cout << ans;
}
int main()
{
    
    int N, M, x;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
    
        cin >> M;
        while (M--)
            cin >> x, v[i].push_back(x), dp[x]++;
    }
    for (int i = 1; i <= N; i++)
        if (!dp[i])
            bfs(i);
    return 0;
}

DFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int n = 1e5 + 10;
int dp[n];
vector<int> v[n];
int ans = 1;
int maxt = 0;
void dfs(int k, int level)
{
    
    if (maxt < level)
        ans = k, maxt = level;
    for (auto &e : v[k])
        dfs(e, level + 1);
}
int main()
{
    
    int N, M, x;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
    
        cin >> M;
        while (M--)
            cin >> x, v[i].push_back(x), dp[x]++;
    }
    for (int i = 1; i <= N; i++)
        if (!dp[i])
            dfs(i, 0);
    cout << ans;
    return 0;
}