[백준 14675번] 파이썬 - 단절점과 단절선

백준 14675 - 단절점과 단절선

시간 제한 1초, 메모리 제한 512MB

# 조건

• 그래프 이론에서 단절점(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개인 경우 루트 노드 또는 리프 노드이므로 no를 출력해주면 된다.
• 또한 간선의 경우, 두 개의 노드를 이어주는 선이기 때문에, 모든 간선은 단절선이다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for _ in range(int(input())):
    t, k = map(int, input().split())
    if t == 2:
        print('yes')
    else:
        if len(tree[k]) < 2:
            print('no')
        else:
            print('yes')