백준 14675 : 단절점과 단절선 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())
Tree=[ [] for _ in range(N+1) ]

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

Q=int(input())

for i in range(Q):
    a,b=map(int,input().split())

    if a==2:
        print("yes")
    else:
        if len(Tree[b])>=2:
            print("yes")
        else:
            print("no")

📌 어떻게 접근할 것인가?

일단 단절점과 단절선에 대해 알아보자.

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

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

📌 단절선

먼저 단절선에 대해 알아보자. 문제에서는 무조건 트리로만 그래프가 주어진다고 명시되어있다.

하지만 트리라는 자료구조를 의미를 잘 보면 다음과 같다.

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

즉 트리는 모든 정점들이 간선으로 연결되어있으며
임의의 간선을 자르면 무조건 그래프가 2개이상으로 나뉘게 된다.

즉 트리에서 간선을 자르게 되면 기존의 그래프와
D - C - E 로 구성된 그래프 둘로 나뉘게 된다.

📌 단절점

그래프의 정점을 제거했을때 그래프가 둘 이상으로 나뉘는 것을 의미한다.
간단하게 생각해보면 리프노드는 제거했을때 그래프가 둘 이상으로 나뉠수 없다.

즉 리프노드가 아닌 모든 정점을 제거하면 그래프가 둘 이상으로 나눌수 있다는 말이다.

따라서 $Q$ 개의 쿼리를 입력받을때 $a$ 가 2이면 무조건 $YES$
$a$ 가 1일때는 $Tree[b]$의 길이가 $2$ 이상이면 단절점이므로 $YES$ , 그렇지 않으면 $NO$ 를 출력한다.