L2-031 深入虎穴 (25 分)

DFS

注意：这道题需要寻找起点，不能自己认为1就是起点。
而且本题编号是从1开始。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> v[maxn];
int inD[maxn]={0};
int maxDepth=0,num=1;
void dfs(int r,int depth){
	
	if(!v[r].size()){ //子节点 
		if(depth > maxDepth){
			maxDepth=depth;
			num=r;
		}
		return; 
	}
	for(int i=0;i<v[r].size();i++){
		int j = v[r][i];
		dfs(j, depth+1);
	}
}
int main(){
	int n,k,tmp;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>k;
		for(int j=0;j<k;j++){
			cin>>tmp;
			v[i].push_back(tmp);
			inD[tmp]++;
		}
	}
	int s;
	for(int i=1;i<=n;i++){ //寻找起点 
		if(inD[i] == 0){
			s = i;
			break;
		}
	}
	dfs(s,0);
	cout<<num<<endl;
	return 0;
}