Sequence Reconstruction

遇到了一题想了半天，觉得自己应该会做，感觉应该像排会议一样用，topological sort, 可又不知道如何抽象成graph node. 又觉得可能可以用union set, 但也不知道怎么写。来来去去想了很多遍，发现还是写不出一行code.

然后看了答案，发现，晕晕晕，真的是用topo sort. 只能怪自己道行不够。。。
然后恍然大悟，好蠢的题目。
做不出题目的我就是好蠢的我。哈哈哈

Description

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example

Given org = [1,2,3], seqs = [[1,2],[1,3]]
Return false
Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Given org = [1,2,3], seqs = [[1,2]]
Return false
Explanation:
The reconstructed sequence can only be [1,2].

Given org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Return true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Given org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Return true

总结：

想要用top sort 必须要把问题抽象成graph, 对于graph有两个重要的东西，vertex和边集。所以简单说来就是如何将问题抽象成边集。

如果 把每个点作为graph node，那么org = [4,1,5,2,6,3]就是它的唯一的top解。

问题又变成了， 已有的边集是否能造就唯一的top解

如何保证top 解的唯一性呢？

queue size = 1

,,,真的是一个“好蠢的问题”。🤣

写了好久，错了好久，对于base case的考虑太不够周详了。

注意奇葩test case:

[ ], [ ], true
[ ], [[ ], [ ]], true
[1], [ ], false
[1], [1], true
[1,2,3,4,5], [[1,2],[1,2,3],[2],[3,4,5],[5,6],[6]], false