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的结点只有一个。

Last updated