444. 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 ≤ 104. 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: 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
```

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.

444. Sequence Reconstruction
``````struct Solution;
use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
fn sequence_reconstruction(org: Vec<i32>, seqs: Vec<Vec<i32>>) -> bool {
let n = org.len();
let mut indegree = vec![0; n];
let mut marked = vec![false; n];
let mut graph = vec![HashSet::new(); n];
for seq in seqs {
let m = seq.len();
for i in 0..m {
let u = (seq[i] - 1) as usize;
if u >= n {
return false;
}
marked[u] = true;
if i + 1 < m {
let v = (seq[i + 1] - 1) as usize;
if v >= n {
return false;
}
if v == u {
return false;
}
if graph[u].insert(v) {
indegree[v] += 1;
}
}
}
}
if marked.iter().any(|x| !x) {
return false;
}
let mut queue: VecDeque<usize> = VecDeque::new();
let mut stack = vec![];
for i in 0..n {
if indegree[i] == 0 {
queue.push_back(i);
}
}
while !queue.is_empty() {
if queue.len() > 1 {
return false;
}
if let Some(u) = queue.pop_front() {
stack.push((u + 1) as i32);
for &v in &graph[u] {
indegree[v] -= 1;
if indegree[v] == 0 {
queue.push_back(v);
}
}
}
}
stack == org
}
}

#[test]
fn test() {
let org = vec![1, 2, 3];
let seqs = vec_vec_i32![[1, 2], [1, 3]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1, 2, 3];
let seqs = vec_vec_i32![[1, 2]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1, 2, 3];
let seqs = vec_vec_i32![[1, 2], [1, 3], [2, 3]];
let res = true;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![4, 1, 5, 2, 6, 3];
let seqs = vec_vec_i32![[5, 2, 6, 3], [4, 1, 5, 2]];
let res = true;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1];
let seqs = vec_vec_i32![];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1];
let seqs = vec_vec_i32![[1, 1]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1, 2];
let seqs = vec_vec_i32![[1, 2], [2, 1]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![3, 2, 1];
let seqs = vec_vec_i32![[1, 2], [1, 3], [2, 3]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
let org = vec![1];
let seqs = vec_vec_i32![[2]];
let res = false;
assert_eq!(Solution::sequence_reconstruction(org, seqs), res);
}
``````