1068번: 트리

https://www.acmicpc.net/problem/1068

indegree를 카운트해서 리프 노드인지 판단한다.
리프 노드로부터 거슬러 올라가다가 제거한 노드를 만나면 해당 노드는 제거된다.
아래 소스의 시간복잡도 $O(n^2)$

#include<cstdio>
int n, p[50], ind[50], g, c;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", p + i);
        if (~p[i]) ind[p[i]]++;
    }
    scanf("%d", &g);
    for (int i = 0; i < n; i++) if (!ind[i]) for (int j = i; ~j; j = p[j]) if (j == g) { c++; break; }
    printf("%d", n / 2 + 1 - c);
    return 0;
}