[BOJ_Python] 14675_단절점과 단절선

 이 문제를 보고 단절선을 찾는 함수 단절점을 찾는 함수를 각각 만들어보려 했는데 도저히 생각이 나지 않았다. 그렇게 문제를 켜두고 생각을 해보니 트리에서 어떤 간선을 없애도 항상 2개의 트리로 나눠진다는 것을 떠올렸고 트리의 끝점 즉, 자식이 없는 노드를 제외하고 나머지 노드를 제거하면 트리는 2개의 트리로 항상 나눠 진다는 것을 생각해냈다. 

 그래서 처음에 graph를 만들 때 빈 리스트가 (노드의 개수 + 1) 개인 2차원 빈 리스트를 만들고 각 리스트에 연결된 노드를 넣었다. (1번 노드와 3번 노드가 연결되어 있으면 1번째 리스트에 3을 넣고 3번째 리스트에 1을 넣는 방식) 그리고 간선을 없앤다고 하면 항상 yes를 출력하게 하고 노드를 없애면 그 노드가 자식이 없는 마지막 노드인지를 확인하고 마지막 노드면 no를 마지막 노드가 아니면 yes를 출력하게 했다. 여기서 마지막 노드인지를 판별하는 방식으론 마지막 노드의 번호에 해당하는 graph의 그 노드 번호에 해당하는 리스트의 원소의 개수가 1인 것을 이용했다.

import sys

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

q = int(input())
for _ in range(q):
    a, b = map(int, sys.stdin.readline().split())
    if a == 2: # 간선을 없애면 항상 yes를 출력하게 하기
        print('yes')
    elif a == 1: 
        if len(graph[b]) == 1: # 제일 끝에 있는 노드인지 판별하기
            print('no')
        else:
            print('yes')

많이 부족하지만 도움이 되셨으면 좋겠습니다!!