사용자 도구

사이트 도구


ps:problems:boj:16314

Kingpin Escape

ps
링크acmicpc.net/…
출처BOJ
문제 번호16314
문제명Kingpin Escape
레벨플래티넘 2
분류

BCC

시간복잡도O(n)
인풋사이즈n<=10^5
사용한 언어Python 3.11
제출기록51000KB / 336ms
최고기록336ms
해결날짜2023/03/11

풀이

  • 문제를 해석하자. 만들어야 하는 그래프는, 엣지가 하나 제거되어도 모든 노드들이 연결되어 있는 그래프, 즉 Bi-Edge-Connected graph이다. 주어진 트리에 최소 갯수의 엣지를 추가해서, Bi-Edge-Connected graph 가 되도록 만들고 싶다.
  • 그래프 전체를 BECC로 만드는 방법 에서 설명한대로, 리프 노드들에만 엣지를 추가해주는 식으로 만들수 있다. 연결할 리프노드쌍을 찾는 것은 DFS order을 이용한다.
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 16314. Kingpin Escape".

- Problem link: https://www.acmicpc.net/problem/16314
- Solution link: http://www.teferi.net/ps/problems/boj/16314

Tags: [graph]
"""

import sys
from teflib import graph as tgraph


def main():
    n, h = [
        int(x) for x in sys.stdin.readline().split()
    ]  # pylint: disable=unused-variable
    tree = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    leaves = [u for u in tgraph.dfs(tree) if len(tree[u]) == 1]

    print((len(leaves) + 1) // 2)
    for u, v in zip(leaves, leaves[(len(leaves) + 1) // 2 :]):
        print(u, v)
    if len(leaves) % 2 == 1:
        print(leaves[len(leaves) // 2], leaves[0])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O V M Z H
 
ps/problems/boj/16314.txt · 마지막으로 수정됨: 2023/03/13 02:40 저자 teferi