[백준][Python] 14675번 단절점과 단절선

14675번: 단절점과 단절선

 

코드

import sys

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

q = int(input())
for _ in range(q):
    t,k = map(int,sys.stdin.readline().split())
    if t == 1:
        if (len(tree[k]) < 2):
            print("no")
        else:
            print("yes")

    elif t == 2:
        print("yes")

 

설명

tree 리스트에 자신과 연결된 노드 번호를 각각 추가시켜주었다.

일단 모든 간선은 단절선이다. 왜냐하면 모든 간선은 노드 2개를 연결하고 있어서 간선을 지우면 트리가 무조건 최소 2개로 나뉘기 때문이다. 따라서 t가 2일 때는 무조건 yes를 출력하게 했다. 

자식이 하나밖에 없는 루트이거나 리프노드일 때 해당 정점을 제거해도 트리가 2개 이상으로 나뉘지 않으므로 이때는 이 정점이 단절점이 아니다. 따라서 tree리스트에서 해당 노드 번호를 인덱스로 하는 부분에 들어있는 숫자의 개수가 1개 이하이면 단절점이 아니기 때문에 no를 출력해줬다.