• Time:Time:
• Space:Space:

## C++

``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
if (seqs.empty())
return false;

const int n = org.size();
vector<vector<int>> graph(n);
vector<int> inDegree(n);

// build graph
for (const auto& seq : seqs) {
if (seq.size() == 1 && seq[0] < 1 || seq[0] > n) {
return false;
} else {
for (int i = 0; i + 1 < seq.size(); ++i) {
const int u = seq[i];
const int v = seq[i + 1];
if (u < 1 || u > n || v < 1 || v > n)
return false;
graph[u - 1].push_back(v - 1);
++inDegree[v - 1];
}
}
}

// topology
queue<int> q;

for (int i = 0; i < n; ++i)
if (inDegree[i] == 0)
q.push(i);

int i = 0;  // org's index

while (!q.empty()) {
if (q.size() > 1)
return false;
const int u = q.front();
q.pop();
if (u != org[i] - 1)
return false;
++i;
for (const int v : graph[u])
if (--inDegree[v] == 0)
q.push(v);
}

return i == n;
}
};
``````

## JAVA

``````class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
if (seqs.isEmpty())
return false;

final int n = org.length;
List<Integer>[] graph = new List[n];
int[] inDegree = new int[n];

for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();

// build graph
for (List<Integer> seq : seqs) {
if (seq.size() == 1 && seq.get(0) < 1 || seq.get(0) > n) {
return false;
} else {
for (int i = 0; i + 1 < seq.size(); ++i) {
final int u = seq.get(i);
final int v = seq.get(i + 1);
if (u < 1 || u > n || v < 1 || v > n)
return false;
++inDegree[v - 1];
}
}
}

// topology
Queue<Integer> q = IntStream.range(0, n)
.filter(i -> inDegree[i] == 0)
.boxed()
.collect(Collectors.toCollection(ArrayDeque::new));

int i = 0; // org's index

while (!q.isEmpty()) {
if (q.size() > 1)
return false;
final int u = q.poll();
if (u != org[i] - 1)
return false;
++i;
for (final int v : graph[u])
if (--inDegree[v] == 0)
q.offer(v);
}

return i == n;
}
}
``````

## Python

``````class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
if not seqs:
return False

n = len(org)
graph = [[] for _ in range(n)]
inDegree = [0] * n

# build graph
for seq in seqs:
if len(seq) == 1 and seq[0] < 1 or seq[0] > n:
return False
else:
for u, v in zip(seq, seq[1:]):
if u < 1 or u > n or v < 1 or v > n:
return False
graph[u - 1].append(v - 1)
inDegree[v - 1] += 1

# topology
q = deque([i for i, d in enumerate(inDegree) if d == 0])
i = 0  # org's index

while q:
if len(q) > 1:
return False
u = q.popleft()
if u != org[i] - 1:
return False
i += 1
for v in graph[u]:
inDegree[v] -= 1
if inDegree[v] == 0:
q.append(v)

return i == n
``````