백준 14675 - 단절점과 단절선 (파이썬)

https://www.acmicpc.net/problem/14675

풀이

그래프의 단절점과 단절선을 판별하는 문제이다.

1. 단절점
   1. 어떤 정점을 제거했을 때 그래프가 여러 개의 컴포넌트로 나뉘는 정점
2. 단절선
   1. 어떤 간선을 제거했을 때 그래프가 여러 개의 컴포넌트로 나뉘는 간선
3. 트리의 간선을 입력받아 입접 리스트를 구성한다.

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

for _ in range(N - 1) :
    u, v = map(int, input().split())

    adj[u - 1].append(v - 1)
    adj[v - 1].append(u - 1)

1. 단절점을 판별한다.

for _ in range(Q) :
    t, k = map(int, input().split())

    if t == 1 :
        if len(adj[k - 1]) == 1 :
            print("no")
        else :
            print("yes")

t == 1 일때 k번 정점이 단절점인지 판별한다.

루트가 아닌 이상, 연결된 간선이 2개 이상이면 단절점이다.

리프 노드는 단절점이 아니기 때문에 no를 출력한다.

그 외에는 단절점이 될수 있으므로 yes를 출력한다.

1. 단절선을 판별한다.

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

t == 2 일때 k번 간선이 단절선인지 판별한다.

트리에서는 모든 간선이 단절선이기 때문에 yes를 출력한다.

시간 복잡도

그래프 입력 : O(N)

처리 : O(1)

전체 시간 복잡도 : O(N + Q)

<aside> 💡

핵심

</aside>

• 트리에서 모든 간선은 단절선이다.
• 리프 노드가 아닌 정점은 단절점이 될 수 있다.
• 단절점 판별은 연결된 간선 개수만 확인하면 된다.

코드

# 백준 14675 - 단절점과 단절선
# 분류 : 그래프

import sys
input = sys.stdin.readline

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

for _ in range(N - 1) :
    u, v = map(int, input().split())

    adj[u - 1].append(v - 1)
    adj[v - 1].append(u - 1)

Q = int(input())

for _ in range(Q) :
    t, k = map(int, input().split())

    if t == 1 :
        if len(adj[k - 1]) == 1 :
            print("no")
        else :
            print("yes")
    if t == 2 :
        print("yes")