Meta 照片顺序恢复：无序相邻对与链端点

题目重点：从无序相邻照片对还原一条序列，识别双向等价、重复边和非链输入。

题意与假设

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

训练照片ID唯一、可比较，pairs是同一简单链所有相邻边，边方向未知；两种朝向都合法，示例选较小端点开始。
空pairs返回[]，只有一张照片的ID无法从无边输入推断，需要额外参数；不能编造照片。

解题路线

构无向邻接，合法链恰两个degree1端点，其余degree2。选一端点，沿邻居不是previous的方向不断走，得到完整顺序。
每条边用frozenset检查重复，a=a自环拒绝；有branch degree>2、纯环无端点、多个component都不满足唯一链。
仅检查degree不足以排除一个链加独立环，因此走完后核对seen数量等于全部节点数。重复访问也作为异常防止无限循环。
照片ID不是坐标大小顺序，min只选朝向端点，内部顺序完全由边决定。不能sort全部ID当序列。

手动走一遍

pairs[(30,10),(20,30)]两朝向为10,30,20与20,30,10；选端点10得到10,30,20，而不是数值排序10,20,30。重复反向边(10,30)/(30,10)仍同一边，训练拒绝。

Python 参考实现

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

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

def restore_photos(pairs):
    """Unique comparable IDs, edges form one simple nonempty chain.

    Either orientation valid; chooses smaller endpoint, rejects cycles/branches.
    One photo with no edges needs separate explicit ID input, not inferable here.
    """
    if not pairs:return []
    graph={};edges=set()
    for a,b in pairs:
        if a==b:raise ValueError('self edge')
        edge=frozenset((a,b))
        if edge in edges:raise ValueError('duplicate edge')
        edges.add(edge);graph.setdefault(a,[]).append(b);graph.setdefault(b,[]).append(a)
    endpoints=[x for x,adj in graph.items() if len(adj)==1]
    if len(endpoints)!=2 or any(len(adj)>2 for adj in graph.values()):raise ValueError('not a path')
    current=min(endpoints);previous=None;result=[];seen=set()
    while current is not None:
        if current in seen:raise ValueError('cycle')
        seen.add(current);result.append(current)
        nexts=[x for x in graph[current] if x!=previous]
        previous,current=current,nexts[0] if nexts else None
    if len(result)!=len(graph):raise ValueError('disconnected')
    return result

复杂度

O(P)平均时间/O(V+P)邻接与seen，合法链P=V−1。端点只有2个选min为常数，不对全部照片排序；输出O(V)。

易错点与追问

容易失分的边界

把输入pair方向当绝对前后，无法连未知朝向边。
有两个端点就宣称所有节点连通，漏独立环。

继续深挖

若照片可重复出现，ID需扩展为位置身份，否则同ID多个位置无法区分。
如果少了一条相邻边，可能多链且无法唯一拼接，应返回不足证据而非猜顺序。