FC深搜DFS-L2-031 深入虎穴
作者:
小花猪
,
2023-04-17 11:03:53
,
所有人可见
,
阅读 177
L2-031 深入虎穴
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5+10;
vector<int> v[N];
int n, len, out, in[N];//len最长路径,out出口
void dfs(int u, int d){
if(!v[u].size()){
if(d > len){
len = d;
out = u;
}
return;
}
for(int i=0; i<v[u].size(); i++){
dfs(v[u][i], d+1);
}
}
int main(){
cin>>n;
for(int i=1; i<=n; i++){//构建邻接表
int k;
cin>>k;
while(k --){
int b;
cin>>b;
v[i].push_back(b);
in[b] = 1;//迷宫只有一个入口
}
}
int root = 0;
for(int i=1; i<=n; i++){//找唯一的入口
if(!in[i]){
root = i;
break;
}
}
dfs(root, 1);
cout<<out<<endl;
return 0;
}