29C - 6 Mail Stamps


题意:从起点按序输出唯一路径
python写一直re,后面发现需要使用sys.setrecursionlimit(int(2 * 10**5))扩大python默认递归深度限制,以达到题目要求
邻接表建图用字典的setdefault方法初始化空列表最简洁

import sys
sys.setrecursionlimit(int(2 * 10**5))
n = int(input())
vised = {}
graph = {}
in_degree = {}
for _ in range(n):
    c1, c2 = map(int, input().split())
    graph.setdefault(c1, []).append(c2)
    graph.setdefault(c2, []).append(c1)
    vised[c1] = 0
    vised[c2] = 0
    in_degree[c1] = in_degree.get(c1, 0) + 1
    in_degree[c2] = in_degree.get(c2, 0) + 1
start = -1
first = 1
for k, v in in_degree.items():
    if v == 1 and first == 1:
        start = k
        first = 0
vised[start] = 1
res = [start]
print(start, end="")
global solved
solved = False
def dfs(u):
    global solved
    if solved:
        return
    if len(res) == len(vised):
        solved = True
        return
    for c in graph[u]:
        if vised[c] == 0:
            vised[c] = 1
            print("", c, end="")
            res.append(c)
            dfs(c)
dfs(start)
# print(*(ans))