多个顺序数组的共同母序列：唯一身份下的拓扑排序

题意与假设

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

• 元素是可排序的唯一身份，各输入内不重复；母序列每身份出现一次，保留每个输入的先后顺序。
• 如果允许母序列重复身份，一般共同超序列总可通过拼接获得，本判环问题不再等价。

解题路线

1. 对每序列的相邻元素加有向边；传递性保证相邻约束足以保留整序列。跨序列重复边只加一次indegree。
2. Kahn从零入度点输出，用最小堆给确定性字典序结果。若输出数小于不同身份总数则存在冲突环，返回None。
3. 两个序列可用局部合并直觉，但多个序列潜在循环跨不同来源，统一图更易证明并产出失败证据。

手动走一遍

[A,B],[A,C],[B,C]得到A,B,C。加入[C,A]形成A→B→C→A，无唯一身份母序列。若允许重复，A,B,C,A仍可包含这些顺序，因此必须先确认“一次出现”约束。

Python 参考实现

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

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

from heapq import heappush,heappop


def mother_sequence(sequences):
    graph,indegree={},{}
    for sequence in sequences:
        if len(sequence)!=len(set(sequence)):
            raise ValueError("identities must occur once per sequence")
        for x in sequence:graph.setdefault(x,set());indegree.setdefault(x,0)
        for u,v in zip(sequence,sequence[1:]):
            if v not in graph[u]:graph[u].add(v);indegree[v]+=1
    heap=[]
    for x,d in indegree.items():
        if d==0:heappush(heap,x)
    result=[]
    while heap:
        u=heappop(heap);result.append(u)
        for v in graph[u]:
            indegree[v]-=1
            if not indegree[v]:heappush(heap,v)
    return result if len(result)==len(indegree) else None

复杂度

总输入长L、V不同身份、E去重相邻边；建图期望O(L)，堆拓扑O((V+E)logV)，空间O(V+E+L)取决于保留输入。

易错点与追问

容易失分的边界

• 重复边若多次indegree++却邻接set只减一次，会误报环。
• 只比较某两序列而忽略第三者可能漏掉全局循环。

继续深挖

• 需要确认解是否唯一时，零入度候选集合怎样判断？
• 输出冲突环和涉及的输入来源，需要记录哪些边证据？