L2-031 深入虎穴（25 分)(天梯赛)

怼烎@ 2022-02-24 21:24 332阅读 0赞

# L2-031 深入虎穴 （25 分) #

[L2-031 深入虎穴 （25 分)][L2-031 _ _25]  
无根变有根,这道题并没有给出入口在哪里，所以需要判断哪个是入口，不要被样例数据误导。然后dfs，找到这棵树的最大深度。

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <set>
    #include <unordered_set>
    using namespace std;
    int t;
    vector<int> vec[100010]; //邻接表
    vector<int> book; //标记入口可以到达的门，当没有路可以到达时，该门就是入口
    int maxn=-1; //标记最远的门到入口的距离
    int m; //标记最远到门
    void dfs(int cur,int ans)
    { 
        if(vec[cur].size()==0)
        { 
            if(maxn<ans) 
            { 
                maxn=ans;
                m=cur;
            }
            return;
        }
        for(int i=0;i<vec[cur].size();i++)
        { 
            dfs(vec[cur][i],ans+1);
        }
    }
    int main()
    { 
        cin>>t; //t表示门的数量
        book.assign(t,0); //book[i]表示有通往该门的路
        for(int i=1;i<=t;i++)
        { 
            int k;
            cin>>k;
            while(k--)
            { 
                int a;
                cin>>a;
                book[a]=1;
                vec[i].push_back(a);
            }
        }
        int sign;
        for(int i=1;i<=t;i++)
        { 
            if(book[i]==0)
            { 
                sign=i; //找到入口
                break;
            }
        }
        dfs(sign,0);
        cout<<m<<endl;
        return 0;
        
    }

[L2-031 _ _25]: https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858888