[ BOJ ] 14675 : 단절점과 단절선 ( SILVER 1 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/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’를 출력한다. 

풀이 과정

트리에서는 특정 간선을 제거하면 무조건 그래프가 2개 이상으로 나뉜다. ( 사이클이 없음 )

특정 정점을 제거할 때, 해당 정점의 자식 노드 수가 2개 이상이라면 그래프가 2개 이상으로 나뉜다.

이를 조건식으로 구현하면 되는 문제이다.

import sys
input = sys.stdin.readline

v = int(input().rstrip())
graph = [{} for _ in range(v+1)]
edges = [list(map(int, input().rstrip().split())) for _ in range(v-1)]
for e in edges:
    a, b = e
    graph[a][b] = 1
    graph[b][a] = 1

q = int(input().rstrip())
for _ in range(q):
    t, k = map(int, input().rstrip().split())
    if t == 1: # k가 단절점인가?
        if len(list(graph[k].keys())) != 1: print('yes')
        else: print('no')
    else: # k가 단절선인가?
        print('yes')