Indeedなう（予選B） C - 木

問題原文

atcoder.jp

解法

「その時点で選べる頂点のうち、番号が最小のものを選ぶ」のが最適。

問題はそのような頂点を高速に取得することだけど、これは優先度付きキューを使うと簡単に実現できる。

実装

import heapq
N = int(input())
T = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)

ans = []
hq = [0]
visited = set()

while hq:
    n = heapq.heappop(hq)
    ans.append(n)
    visited.add(n)
    for to in T[n]:
        if to in visited:
            continue
        heapq.heappush(hq, to)

print(*[a + 1 for a in ans], sep=' ')

感想

推定水diffらしい。
今だと下手すると茶diffがつきかねないなぁという印象。