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
Example 1:
Input:org = [1,2,3], seqs = [[1,2],[1,3]]
Output: 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.
Example 2:
Input: org = [1,2,3], seqs = [[1,2]]
Output: false
Explanation:
The reconstructed sequence can only be [1,2].
Example 3:
Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Output: true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Example 4:
Input:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Output:true
思路：
剛開始看題可能比較糊涂，最后會發(fā)現(xiàn)實(shí)際上是判斷org是否是seqs的唯一拓?fù)渑判颍?就轉(zhuǎn)換成BFS求拓?fù)渑判虻膯栴}， 難點(diǎn)就是如何構(gòu)件圖及獲得每個(gè)點(diǎn)的入度， 這個(gè)題先得到了每個(gè)點(diǎn)后續(xù)的點(diǎn)，并且用set排除了重復(fù)的可能， 然后根據(jù)這個(gè)信息去計(jì)算入度。
還要注意是否存在唯一拓?fù)湫虻臈l件是隊(duì)列中是否永遠(yuǎn)只有一個(gè)點(diǎn)，即不存在分叉。
還有結(jié)構(gòu)化的編程會讓代碼可讀性增強(qiáng)。
代碼：
