15900번: 나무 탈출

문제접근🤔

놓쳤던 부분😅

• 문제를 제대로 이해를 못함. 이기는 방법에 대한 아이디어를 떠올리지 못함

코드😁

53844 KB

392 ms

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int> > tree;
vector<bool> visited;
int cnt = 0;

void dfs(int node, int depth) {
	if (tree[node].size() == 1 && visited[tree[node][0]]) {
		if (depth % 2 == 1)
			cnt++;
		return ;
	}
	for (unsigned int i = 0; i < tree[node].size(); i++) {
		int nextNode = tree[node][i];

		if (visited[nextNode])
			continue ;
		visited[nextNode] = true;
		dfs(nextNode, depth + 1);
		visited[nextNode] = false;
	}
}

int main(void) {
	int n;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	tree.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < n - 1; i++) {
		int input1, input2;

		cin >> input1 >> input2;
		tree[input1].push_back(input2);
		tree[input2].push_back(input1);
	}

	visited[1] = true;
	dfs(1, 0);

	if (cnt % 2 == 1)
		cout << "Yes";
	else
		cout << "No";
	return (0);
}