https://www.acmicpc.net/problem/1068
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<vector<int>> node;
int N;
int answer = 0;
int target;
void Count(int now_node) {
if (now_node == target) return;
int now_node_size = node[now_node].size();
switch (now_node_size) {
case 0:
answer++; return;
break;
case 1:
if (node[now_node][0] == target) {
answer++;
break;
}
default:
for (int i = 0; i < now_node_size; i++) {
Count(node[now_node][i]);
}
break;
}
}
int main() {
cin >> N;
node.resize(N);
int root;
for (int i = 0; i < N; i++) {
int input;
cin >> input;
if (input == -1) {
root = i;
}
else {
node[input].push_back(i);
}
}
cin >> target;
if (target == 0) {
cout << 0 << "\n";
}
else {
Count(root);
cout << answer;
}
return 0;
}
설계
