验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。序列 org 是 1 到 n 整数的排列，其中 1 ≤ n ≤ 104 。重建是指在序列集 seqs 中构建最短的公共超序列。（即使得所有 seqs 中的序列都是该最短序列的子序列）。请你确定是否只可以从 seqs 重建唯一的序列，且该序列就是 org 。
示例 1：
输入：org = [1,2,3], seqs = [[1,2],[1,3]] 输出：false 解释：[1,2,3] 不是唯一的可重建序列，[1,3,2] 也是一个有效的可重建序列。
示例 2：
输入：org = [1,2,3], seqs = [[1,2]] 输出：false 解释：可重建序列只能是 [1,2] 。
示例 3：
输入：org = [1,2,3], seqs = [[1,2],[1,3],[2,3]] 输出：true 解释：序列 [1,2]、[1,3] 和 [2,3] 可以从原始序列 [1,2,3] 唯一地重建。
示例 4：
输入：org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]] 输出：true
提示：
1 <= n <= 10^4org是{1,2,...,n}的一个排列1 <= segs[i].length <= 10^5seqs[i][j]符合 32 位整数范围
拓扑排序，BFS 实现。
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
n = len(org)
nums = set()
for seq in seqs:
for num in seq:
if num < 1 or num > n:
return False
nums.add(num)
if len(nums) < n:
return False
edges = defaultdict(list)
indegree = [0] * (n + 1)
for seq in seqs:
i = seq[0]
for j in seq[1:]:
edges[i].append(j)
indegree[j] += 1
i = j
q = deque()
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
cnt = 0
while q:
if len(q) > 1 or org[cnt] != q[0]:
return False
i = q.popleft()
cnt += 1
for j in edges[i]:
indegree[j] -= 1
if indegree[j] == 0:
q.append(j)
return cnt == nclass Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
int n = org.length;
Set<Integer> nums = new HashSet<>();
for (List<Integer> seq : seqs) {
for (int num : seq) {
if (num < 1 || num > n) {
return false;
}
nums.add(num);
}
}
if (nums.size() < n) {
return false;
}
List<Integer>[] edges = new List[n + 1];
for (int i = 0; i < edges.length; ++i) {
edges[i] = new ArrayList<>();
}
int[] indegree = new int[n + 1];
for (List<Integer> seq : seqs) {
int i = seq.get(0);
for (int j = 1; j < seq.size(); ++j) {
edges[i].add(seq.get(j));
++indegree[seq.get(j)];
i = seq.get(j);
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; ++i) {
if (indegree[i] == 0) {
q.offer(i);
}
}
int cnt = 0;
while (!q.isEmpty()) {
if (q.size() > 1 || q.peek() != org[cnt]) {
return false;
}
++cnt;
int i = q.poll();
for (int j : edges[i]) {
--indegree[j];
if (indegree[j] == 0) {
q.offer(j);
}
}
}
return cnt == n;
}
}class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
int n = org.size();
unordered_set<int> nums;
for (auto& seq : seqs)
{
for (int num : seq)
{
if (num < 1 || num > n) return false;
nums.insert(num);
}
}
if (nums.size() < n) return false;
vector<vector<int>> edges(n + 1);
vector<int> indegree(n + 1);
for (auto& seq : seqs)
{
int i = seq[0];
for (int j = 1; j < seq.size(); ++j)
{
edges[i].push_back(seq[j]);
++indegree[seq[j]];
i = seq[j];
}
}
queue<int> q;
for (int i = 1; i <= n; ++i)
{
if (indegree[i] == 0) q.push(i);
}
int cnt = 0;
while (!q.empty())
{
if (q.size() > 1 || q.front() != org[cnt]) return false;
++cnt;
int i = q.front();
q.pop();
for (int j : edges[i])
{
--indegree[j];
if (indegree[j] == 0) q.push(j);
}
}
return cnt == n;
}
};func sequenceReconstruction(org []int, seqs [][]int) bool {
n := len(org)
nums := make(map[int]bool)
for _, seq := range seqs {
for _, num := range seq {
if num < 1 || num > n {
return false
}
nums[num] = true
}
}
if len(nums) < n {
return false
}
edges := make([][]int, n+1)
indegree := make([]int, n+1)
for _, seq := range seqs {
i := seq[0]
for _, j := range seq[1:] {
edges[i] = append(edges[i], j)
indegree[j]++
i = j
}
}
var q []int
for i := 1; i <= n; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}
cnt := 0
for len(q) > 0 {
if len(q) > 1 || org[cnt] != q[0] {
return false
}
i := q[0]
q = q[1:]
cnt++
for _, j := range edges[i] {
indegree[j]--
if indegree[j] == 0 {
q = append(q, j)
}
}
}
return cnt == n
}