Codeforces 116C Party 树+dfs

点击打开链接

题意:森林有n个结点,n<=2e3.一个group中任意两个人不为祖先关系,求最少能分多少个group 若某个树的高度为h 则至少要分h组,若把每个高度的分在一组则只要h组,不同的树可以分在同一个组 所以ans=max(hi) 

#include <bits/stdc++.h> using namespace std; const int N=2e5+20; int vis[N],ans,a[N]; vector<int> e[N]; void dfs(int u,int fa,int h) { vis[u]=1; ans=max(h,ans); for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(vis[v]==0) dfs(v,u,h+1); } } int main() { int n,m; while(cin>>n) { ans=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int v; cin>>v; a[i]=v; if(v==-1) continue; e[i].push_back(v); e[v].push_back(i); } for(int i=1;i<=n;i++) { if(a[i]==-1) dfs(i,-1,1); } cout<<ans<<endl; } return 0; }