Codeforces #87 div2 C "Party"
問題:http://codeforces.com/contest/116/problem/C
人数と直属の上司がだれかが与えられる.グループにわけるとき,一つのグループには上下関係が存在しないようにする場合の最小で分けられるグループ数を求める.
上下関係は木構造で表されるので,Depthが上下関係を最小で分割できる数になるのでリーフからルートまでをたどっていってDepthを得るだけ.
import java.util.*; public class C { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = s.nextInt(); } int max = 0; for(int i = 0; i < n; ++i){ max = Math.max(max, f(i, 1)); } System.out.println(max); } static int[] a; static int f(int i, int d){ if(a[i] < 0){ return d; }else{ return f(a[i]-1, d + 1); } } }