LeetCode 2097代码超时疑惑：x=-1初始化为何拖慢性能及命名空间差异

问题背景 #

提交的代码如下：

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        G = defaultdict(list)
        d = defaultdict(int)
        
        for x, y in pairs:
            G[x].append(y)
            d[x] += 1
            d[y] -= 1
        
        x = -1
        for k in d:
            if d[k] == 1:
                x = k
                break
        
        ans = []
        def dfs(v):
            while G[v]:
                dfs(G[v].pop())
            ans.append(v)
        
        dfs(x)
        ans.reverse()
        return [[ans[i], ans[i+1]] for i in range(len(ans)-1)]

这段代码因输出错误（你误判为超时）无法通过，但删除x = -1初始化语句后即可通过。以下是两个问题的解答：

1. 初始化x=-1导致程序异常的原因 #

当输入的数对构成欧拉图（所有节点的入度等于出度）时，遍历d字典的循环找不到d[k]==1的节点（这类节点是欧拉路径的起点），此时x会保留初始值-1。

调用dfs(-1)时，G[-1]是defaultdict(list)自动生成的空列表，dfs函数会直接将-1加入ans数组，最终反转后得到的ans仅包含-1，返回的结果是空列表，完全不符合题目要求的有效排列。

而删除x=-1后，x的值是第一个for循环最后一次迭代的节点值（该节点必然存在于图中），此时调用dfs(x)可以正确遍历整个欧拉图，生成符合要求的有效排列。

2. Python无需初始化x即可正常运行的原因 #

Python采用名字绑定的变量机制：变量名是对对象的引用，必须先绑定到某个对象（即完成赋值）才能被引用。在你的代码中，x已经在第一个for x, y in pairs:循环中被多次赋值，后续使用时x必然指向一个存在于图中的节点，因此无需额外初始化。

而C++等静态类型语言基于内存分配机制：声明变量时会直接分配内存，但未初始化时内存中是随机的垃圾值，直接使用会导致未定义行为。这是两种语言变量模型的本质差异，和命名空间机制无关。

内容的提问来源于stack exchange，提问作者srm26