codeforces 115A A. Party

2015-12-05 · 1 min read · dfs tree

http://codeforces.com/problemset/problem/115/A 题意：给出n个人之间的上级下级关系。问如何分得最少的组，使得没一组中的人不存在上下级关系。思路：用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点，不存在上下级关系，可以放在一个group.对于同一棵树，每一层要单独放一个group.所以答案是所有树的深度的最大值。

/* ***********************************************
Author :111qqz
Created Time :2015年12月04日 星期五 21时31分38秒
File Name :code/cf/problem/115A.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;

1const int N=2E3+7;
2int p[N];
3int f[N];

1int n;
2int ans;
3int main()
4{
5	#ifndef  ONLINE_JUDGE 
6	freopen("code/in.txt","r",stdin);
7  #endif

 1	scanf("%d",&n);
 2	for (  int i = 1 ; i <= n ; i++) scanf("%d",&p[i]);
 3	ans = -1;
 4	for ( int i = 1 ; i <= n ; i++)
 5	{
 6	    int depth = 1;
 7	    int id = i;
 8	    while (p[id]!=-1)
 9	    {
10		depth++;
11		id = p[id];
12	    }
13	    if (depth>ans) ans = depth; 
14	}
15	printf("%d\n",ans);

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}