> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0444_sequence_reconstruction/slt.md).

# slt

能唯一重建的意思就是任意两个数字的顺序必须是一致的，不能说在一个子序列中1在4的后面， 但是在另一个子序列中1在4的前面，这样就不是唯一的了。 还有一点就是，子序列seqs中不能出现其他的数字，就是说必须都是原序列中的数字。

## 思路1 拓扑排序

拓扑排序本身的结果不一定是唯一的，这道题要求是唯一的一个org，即要求拓扑排序的结果是唯一的，即每次入度为0的结点只有一个。

将seqs中的各序列seq按照其中元素出现的先后顺序建立有向图g。 例如seqs中的某序列seq = \[1, 2, 3]，对应有向图，顶点为1, 2, 3；边为(1, 2), (2, 3)。

然后对图g执行拓扑排序，将得到的排序结果与原始序列org作比对即可。

其实也不用把拓扑排序的结果求出来：

对于一个有向图，当无环时存在拓扑排序；而唯一确定则表示拓扑排序每一层只有一个结点，且整个图是连通的，这意味这在拓扑排序的过程中，每次入度为0的结点只有一个。