一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
1131F - Asya And Kittens
二、解题报告
1、思路分析
本质是拼积木游戏
初始有n块积木,每次两块首尾拼成一块就行,拼接n - 1 次最后会得到一个大积木,我们从左往右输出组成大积木的每一块小积木的编号即可
考虑用并查集来维护每块小积木在哪个积木块,祖先即积木块的起始块,为了合并,额外维护每块大积木的末尾块
然后直接模拟即可
2、复杂度
时间复杂度: O(N)空间复杂度:O(N)
3、代码详解
import sys
input = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
II = lambda: int(input())
P = 998244353
def solve():
n = II()
p = [-1] * n
ed = list(range(n))
nxt = [-1] * n
def find(x: int) -> int:
if p[x] < 0:
return x
p[x] = find(p[x])
return p[x]
def merge(x: int, y: int) -> None:
px, py = find(x), find(y)
if px == py:
return
if p[px] > p[py]:
px, py = py, px
p[px] += p[py]
p[py] = px
nxt[ed[px]] = py
ed[px] = ed[py]
for i in range(n - 1):
a, b = MII()
merge(a - 1, b - 1)
res = [find(0)]
for i in range(n - 1):
res.append(nxt[res[-1]])
print(' '.join(str(x + 1) for x in res))
if __name__ == "__main__":
solve()