[Python] 백준 14675 - 단절점과 단절선 문제 풀이

Overview

BOJ 14675번 단절점과 단절선 Python 문제 풀이
분류: tree (트리)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from collections import defaultdict


def is_cut_vertex(tree, vertex: int) -> None:
    if len(tree[vertex]) < 2:
        print('no')
    else:
        print('yes')


def is_bridge(tree, edge) -> None:
    print('yes')


def main():
    def input():
        return stdin.readline()

    tree = defaultdict(list)
    edges = [(0, 0)]

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

    q = int(input())
    for _ in range(q):
        t, k = map(int, input().split())
        if t == 1:
            is_cut_vertex(tree, k)
        else:
            is_bridge(tree, edges[k])


if __name__ == "__main__":
    main()

트리에서 단절점이 아닌 노드는 자식이 하나인 루트 노드와 리프 노드이다. 따라서 진출차수가 1개이면 단절점이 아니다.

트리는 사이클이 존재하지 않으므로 모든 간선이 단절선이다. 따라서 항상 yes를 출력한다.