백준 1068 c++ 트리 그래프문제

1068번: 트리

 

아아 이 문제는 어떻게 풀어야할까?.....

일단 대강 읽어보면

1. 그래프를 입력한다.

2. 중간에 노드를 끊어낸다.

3. 리프노드의 개수를 알아낸다. 

이정도인 것 같다.

 

그렇다면.. dsf 돌리면서 자식 노드가 없다면 리프노드일 것이고.. 계속 잘라진 노드인지 확인하면 될 것이다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> v;
int root = -1;
int deleteNode = -1;
int leafNode = 0;

void dfs(int st) {

	if (st == deleteNode)
		return;

	bool isleaf = true;

	for (int i : v[st]) {
		if (i != deleteNode) {
			isleaf = false;
			dfs(i);
		}
	}

	if (isleaf)
		leafNode++;
}

int main() {

	int n;

	cin >> n;
	v.resize(n);

	for (int i = 0; i < n; i++) {
	
		int parent;
		cin >> parent;
		if (parent == -1)
			root = i;
		else {
			v[parent].push_back(i);
		}

	}

	cin >> deleteNode;

	if (deleteNode == root)
		cout << '0' << endl;
	else {
		dfs(root);
		cout << leafNode << endl;
	}

	return 0;
}