[BOJ/Gold 5] 백준 14675 단절점과 단절선(C++)

문제 링크

https://www.acmicpc.net/problem/14675

14675번: 단절점과 단절선

 

문제

그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다.

• 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다.
• 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다.

이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다.

• 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프

트리의 정보와 질의가 주어질 때, 질의에 대한 답을 하시오. 

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정보 a, b가 주어진다. 이는 a정점과 b정점이 연결되어 있다는 뜻이며, 입력으로 주어지는 정보는 트리임이 보장된다. (1 ≤ a, b ≤ N)

다음 줄에는 질의의 개수 q가 주어진다. (1 ≤ q ≤ 100,000) 다음 q줄에는 질의 t k가 주어진다. (1 ≤ t ≤ 2) t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다. t가 1일 때는 (1 ≤ k ≤ n)이며, t가 2일 때는 (1 ≤ k ≤ n - 1)이다. 

출력

프로그램의 출력은 표준 출력으로 한다. q줄에 대하여 해당 질의에 대한 답을 한다. 각각은 개행으로 구분하며, 질의가 맞다면 ‘yes’를, 질의가 틀리면 ‘no’를 출력한다. 

예제 입력 1

5
1 2
2 3
3 4
4 5
4
1 1
1 2
2 1
2 2

예제 출력 1

no
yes
yes
yes

알고리즘 분류

• 그래프 탐색

풀이

문제에서는 주어지는 입력은 무조건 트리를 이루게 되어 있다고 하였다.

트리에서 모든 간선은 단절선이 되고, 끝 정점이 아니라면 단절점이 된다.

따라서 T가 2라면 무조건 yes를 출력하고, T가 1이면 Tree[K]의 크기가 2 이상이라면 yes, 그게 아니라면 no를 출력한다.

Tree[K]의 크기가 1이라면 끝 정점을 의미하는 것이기 때문이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, Q;
vector<int> Tree[MAX];

void Input() {
	cin >> N;
	for (int i = 0; i < (N - 1); i++) {
		int A, B;
		cin >> A >> B;
		Tree[A].push_back(B);
		Tree[B].push_back(A);
	}
	cin >> Q;
}

void Find_Answer() {
	while (Q--) {
		int T, K;
		cin >> T >> K;
		if (T == 1) { // K번 정점이 단절점인가?
			if (Tree[K].size() >= 2) {
				cout << "yes\n";
			}
			else {
				cout << "no\n";
			}
		}
		else if (T == 2) { // K번째 간선이 단절선인가?
			cout << "yes\n";
		}
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}