预计阅读时间：2 分钟
图论
图论一类题的合集，随训练持续补完。用 Python 打 CF，除了算法本身，还得和语言特性过几招——这类实战经验也一并记录在此。
DFS 与建图
CF 29C - Mail Stamps（唯一路径重建）
题意：给出无序的边集，它们构成一条链，从端点按序输出这条唯一路径。
思路本身朴素：度为 1 的点是端点，从任一端点 dfs 走到底即可。这题真正的收获是两条 Python 实战经验：
- 交上去一直 RE，根因不是算法：Python 默认递归深度限制只有 1000，链长 $10^5$ 的 dfs 直接爆栈。需要
sys.setrecursionlimit(int(2 * 10**5))把递归深度扩到题目规模。 - 邻接表建图用字典的
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="")
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)
solved = False
dfs(start)
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。