A company has n employees numbered from 1 to n. Each employee either has no immediate manager or exactly one immediate manager, who is another employee with a different number. An employee A is said to be the superior of another employee B if at least one of the following is true:
The company will not have a managerial cycle. That is, there will not exist an employee who is the superior of his/her own immediate manager.
Today the company is going to arrange a party. This involves dividing all n employees into several groups: every employee must belong to exactly one group. Furthermore, within any single group, there must not be two employees A and B such that A is the superior of B.
What is the minimum number of groups that must be formed?
The first line contains integer n (1?≤?n?≤?2000) — the number of employees.
The next n lines contain the integers pi (1?≤?pi?≤?n or pi?=?-1). Every pi denotes the immediate manager for the i-th employee. If pi is -1, that means that the i-th employee does not have an immediate manager.
It is guaranteed, that no employee will be the immediate manager of him/herself (pi?≠?i). Also, there will be no managerial cycles.
Print a single integer denoting the minimum number of groups that will be formed in the party.
5
-1
1
2
1
-1
3
思路：求树的高度。用并查集，不要压缩路径。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int father[2005], cnt; 6 int max(int x, int y) 7 { 8 return x > y ? x : y; 9 } 10 void init(int n) 11 { 12 for(int i = 1;i <= n;i ++) 13 father[i] = i; 14 } 15 16 void find(int x) 17 { 18 if(x == father[x]) 19 return; 20 cnt ++; 21 find(father[x]); 22 } 23 24 void unit(int x, int y) 25 { 26 father[x] = y; 27 return ; 28 } 29 30 int main(int argc, char const *argv[]) 31 { 32 int n, ans, temp; 33 while(~scanf("%d", &n)) 34 { 35 init(n); 36 for(int i = 1;i <= n;i ++) 37 { 38 scanf("%d", &temp); 39 if(temp != -1) 40 unit(i, temp); 41 } 42 ans = 0; 43 for(int i = 1;i <= n;i ++) 44 { 45 cnt = 0; 46 find(i); 47 ans = max(ans, cnt); 48 } 49 printf("%d\n", ans+1); 50 } 51 return 0; 52 }
codeforces --- 115A,布布扣,bubuko.com
原文：http://www.cnblogs.com/anhuizhiye/p/3603585.html