L2-031 深入虎穴 (25 分)

 1.题意　

　　情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门，不存在两条路通向同一扇门，找出距离入口最远的那扇门。给定门的数量N，接下来 N 行，第 i 行描述编号为 i 的那扇门背后能通向的门。在一行中输出距离入口最远的那扇门的编号。

 2.题解

　　题目没给入口，先把入口找到，因为没有哪扇门会通向入口，所以用vis数组记录每个门是否被通向，没被通向的那扇门就是入口。用vector数组存每扇门通往的门，再用dfs搜到最深点，特判只有一扇门的情况，直接输出1。

3.代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 5;
 4 int n, ru;
 5 int vis[maxn];
 6 vector<int> mp[maxn];
 7 int mmax = 0;
 8 int ans = 0;
 9 void dfs(int pr, int cnt) {
10     if(mp[pr].size() == 0) {
11         if(cnt > mmax) {
12             ans = pr;
13             mmax = cnt;
14         }
15         return;
16     }
17     
18     for(int i = 0; i < (int)mp[pr].size(); i++) {
19         dfs(mp[pr][i], cnt + 1);
20     }
21 }
22 int main() {
23     cin >> n;
24     for(int i = 1; i <= n; i++) {
25         int k;
26         cin >> k;
27         int x;
28         for(int j = 1; j <= k; j++) {
29             cin >> x;
30             mp[i].push_back(x);
31             vis[x] = 1;
32         }
33     }
34     
35     if(n == 1) {
36         cout << 1 << endl;
37         return 0;
38     }
39     
40     for(int i = 1; i <= n; i++) {
41         if(vis[i] == 0) {
42             ru = i;
43             break;
44         }
45     } 
46     
47     dfs(ru, 0);
48     
49     cout << ans << endl;
50     
51     return 0;
52 } 

View Code