首页 > 代码库 > zoj 3805 Machine

zoj 3805 Machine

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5337

 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6  7 vector<int>g[1001100]; 8 int a[100101]; 9 int in[100101];10 int n;11 int dfs(int u)12 {13     int c,x;14     if(in[u]==0) return 1;15     if(in[u]==1)16     {17         c=dfs(g[u][0]);18         return c;19     }20     else21     {22         c=dfs(g[u][0]);23         x=dfs(g[u][1]);24         if(c!=x) return max(x,c);25         else return c+1;26     }27 28 }29 30 int main()31 {32    while(scanf("%d",&n)!=EOF)33    {34        for(int i=1; i<=n; i++)35        {36            g[i].clear();37        }38        memset(in,0,sizeof(in));39        for(int i=1; i<=n-1; i++)40        {41            scanf("%d",&a[i]);42            g[a[i]].push_back(i+1);43            in[a[i]]++;44        }45        printf("%d\n",dfs(1));46    }47    return 0;48 }
View Code

 

zoj 3805 Machine