TikTok 景点邻接对还原：链端点与结构验证

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练无向、不重复、无自环的相邻对，所有顶点形成一条simple chain；空对返回空。
• 描述样例是一条链，其他图类型未明确，因此代码验证并拒绝分叉/环/不连通，不擅自求Hamiltonian路径。

解题路线

1. 建立无向邻接表，链应恰有两个度1端点，其余度2。选一个端点，沿唯一未访问邻居前进。
2. 访问数量必须等于全部顶点，防另一不连通环在度数检查中漏掉。重复无向边与自环提前拒绝。
3. 反方向结果同样有效，不能要求输入pair第一个点就是起点；pair方向与顺序不影响链。
4. 如果只需walk覆盖边或每顶点一次，一般图问题不同；先确认目标，不能默认都能线性还原。

手动走一遍

[[1,5],[5,3],[3,2],[2,4]]输出1,5,3,2,4或逆序；打乱pair/反转各对仍相同。[(1,2),(2,3),(2,4)]分叉，本文拒绝；[(1,2),(3,4)]不连通也拒绝。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def restore_path(pairs):
    """Distinct undirected edges guaranteed to form one simple chain.
    Validate non-chain/cyclic/disconnected structures rather than guess a route."""
    if not pairs:
        return []
    graph={};edges=set()
    for a,b in pairs:
        key=frozenset((a,b))
        if a==b or key in edges:
            raise ValueError('self or duplicate edge')
        edges.add(key);graph.setdefault(a,[]).append(b);graph.setdefault(b,[]).append(a)
    endpoints=[v for v,neighbors in graph.items() if len(neighbors)==1]
    if len(endpoints)!=2 or any(len(n)>2 for n in graph.values()):
        raise ValueError('not one simple chain')
    result=[];current=endpoints[0];seen=set()
    while True:
        seen.add(current);result.append(current)
        candidates=[v for v in graph[current] if v not in seen]
        if not candidates:
            break
        current=candidates[0]
    if len(result)!=len(graph):
        raise ValueError('disconnected or cyclic component')
    return result

复杂度

V顶点E边 O(V+E)时间与空间，链E=V−1。输出O(V)，基于哈希平均成本。

易错点与追问

容易失分的边界

• 只查度数不查覆盖数量。
• 把pair顺序当路线顺序。
• 分叉图强行挑一个邻居遗漏。

继续深挖

• 若是环要怎样定义起点？
• 如果输入保证合法是否仍做校验？