1068_트리

 

루트 노드가 무조건 노드 0 이라고 생각하고 풀었는데 0이 아닐 수도 있다.

트리 는 벡터 배열을 이용해 나타냈다.
노드 i의 자식 노드는 adj[i]에 push한다.

 

#include<bits/stdc++.h>
using namespace std;
int ret=0,r,root,n,num;
vector <int> adj[100];
void dfs(int here) {
	int child = 0;
	for (int i=0;i<adj[here].size();i++) {
		int there=adj[here][i];
		if (there == r) continue;
		dfs(there);
		child++;
	}
	if (child == 0)
		ret++;

}
int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if(num==-1)
			root=i; //루트 노드가 0 이 아닐 수 있다. 
		else
			adj[num].push_back(i);
	}

	cin >> r;
	if (r == root) {
		cout << "0\n"; return 0;
	}
	dfs(root);

	cout << ret;
	return 0;
}