Kingpin Escape

• 문제를 해석하자. 만들어야 하는 그래프는, 엣지가 하나 제거되어도 모든 노드들이 연결되어 있는 그래프, 즉 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()

• Dependency: teflib.graph.dfs