[C++] 백준 14675번 - 단절점과 단절선

골드문제라 겁먹었지만 Tree개념을 제대로만 알고 있다면 어려운 문제는 아니었다.

먼저 단절점에 대해서 생각을 해보자.

단절점에서 해당 vertex가 삭제가 되었는데, child가 없다면 해당 vertex는 단절점이 아니고, 그래프로 하나로 유지될 것이다. 따라서 해당 vertex의 size가 1 초과라면 당연히 해당 정점은 단절점이 된다.

반면 단절선은 무의미하다. 편향 tree라고 하더라도 간선을 하나 자르면 무조건 그래프는 2개 이상으로 쪼개진다. 

이 점을 고려하여 잘 그림만 그려도 쉽게 풀 수 있다. 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, q, t, k;
vector<int> tree[100001];

int main() {

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

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y; cin >> x >> y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}

	cin >> q;
	while (q--) {
		cin >> t >> k;
		switch (t) {
		case 1:
			if (tree[k].size() > 1) {
				cout << "yes" << endl;
			}
			else cout << "no" << endl;
			break;
		case 2:
			cout << "yes" << endl;
			break;
		default:
			break;
		}
	}

	return 0;
}