## Description

https://leetcode.com/problems/sequence-reconstruction/

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 1:**

Input:org = [1,2,3], seqs = [[1,2],[1,3]]Output:falseExplanation:[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:falseExplanation:The reconstructed sequence can only be [1,2].

**Example 3:**

Input:org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]Output:trueExplanation: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

**Constraints:**

`1 <= n <= 10^4`

`org`

is a permutation of {1,2,…,n}.`1 <= segs[i].length <= 10^5`

`seqs[i][j]`

fits in a 32-bit signed integer.

**UPDATE (2017/1/8):**

The *seqs* parameter had been changed to a list of list of strings (instead of a 2d array of strings). Please reload the code definition to get the latest changes.

## Python Solution

Check if the result of topological order of sequences is the same as the given order.

```
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
graph = self.build_graph(seqs)
topological_order = self.topological_sort(graph)
return topological_order == org
def build_graph(self, seqs):
graph = {}
for seq in seqs:
for node in seq:
if node not in graph:
graph[node] = set()
for seq in seqs:
for i in range(1, len(seq)):
graph[seq[i - 1]].add(seq[i])
return graph
def topological_sort(self, graph):
indegrees = {
node: 0 for node in graph
}
for node in graph:
for neighbor in graph[node]:
indegrees[neighbor] += 1
topological_order = []
queue = deque()
for node in graph:
if indegrees[node] == 0:
queue.append(node)
while queue:
if len(queue) > 1:
return None
node = queue.popleft()
topological_order.append(node)
for neighbor in graph[node]:
indegrees[neighbor] -= 1
if indegrees[neighbor] == 0:
queue.append(neighbor)
if len(topological_order) == len(graph):
return topological_order
return None
```

- Time Complexity: O(N).
- Space Complexity: O(N).