LeetCode Solutions

			

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 vector<int>& 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;
  }
};

			

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;
          graph[u - 1].add(v - 1);
          ++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;
  }
}

			

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