단절점과 단절선(백준 14675번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가? ✓

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?✓

---

난이도 체감

1. 최상

2. 상

3. 중✓

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

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

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

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

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

나의 풀이(정답 참고)

import sys
input=sys.stdin.readline
N=int(input().strip())
tree_list=[0]*(N+1)
for _ in range(N-1):
    n1,n2=map(int,input().strip().split())
    tree_list[n1]+=1
    tree_list[n2]+=1
q=int(input().strip())
for _ in range(q):
    ne,num=map(int,input().strip().split())
    if ne==2:
        print('yes')
    else:
        if tree_list[num]==1:
            print('no')
        else:
            print('yes')

• 우선 중요한 것은, edge를 없애면 항상 2개의 tree가 만들어진다는 것이다.(이것 때문에 정답을 참고했는데, 생각해보니 당연했다)
• 따라서 2가 입력이 된다면 항상 ‘yes’를 출력하도록 하였다.
• node를 없애는 경우에, 연결된 node의 개수가 1개인 node를 없애면 2개의 tree가 만들어지지 않는다.
  • ex) child가 1개인 root 또는 leaf node
• 따라서 입력을 받아, 각 node가 몇개의 node와 연결되어있는지 유지하는 tree_list를 통해 구분했다.