題目網址：https://leetcode.cn/problems/sequence-reconstruction/

題意：給一 [1, n] 長度為 n 的整數 array nums, 以及一些 2d 整數 array sequences, 其中 sequences[i] 是 nums 的 subsequence。

返回 sequences 是否能唯一重建出 nums。

e.g. nums = [1,2,3], sequences = [[1,2], [1,3]]

  • sequences 可重建出 [1,2,3] 和 [1,3,2] 並不唯一, 故返回 false。因為 1 必須在 2、3 的前面, 但 2 和 3 間並沒有唯一的順序
  • 但若更改 sequences = [[1,2], [1,3], [2,3]], 則可唯一重建出 [1,2,3], 故返回 true。因為 1 必須在 2、3 的前面, 且 2 必須在 3 的前面, 故只能重建出 [1,2,3]

Solution：

想法：利用 Topological Sort + BFS, 將 sequences 轉成有向圖, 給定的順序 nums 等價於有向圖的 Topological Sort

  • 首先, 計算每個點的 inDegree
  • 將所有 inDegree = 0 的 node 加到 queue 中, 並進行 Topological Sort
  • queue 中的元素個數表示可以作為下一個數字的元素個數
    • 若 queue 中的元素個數 > 1, 則下一個數字並不唯一, 應返回 false
    • 若 queue 中的元素個數 = 1, 則下一個數字是唯一的數字。並將該數字從 queue 取出, 且該數字指向的每個數字的 inDegree - 1, 並將 inDegree 變成 0 的數字加到 queue 中
class Solution {
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
        const int n = nums.size();
        vector<int> inDegree(n + 1, 0); // nums 由 [1, n] 組成, 而非 [0, n-1]
        vector<unordered_set<int>> adj(n + 1); // adjacency list

        for (const auto& seq : sequences) {
            for (int i = 1; i < seq.size(); ++i) {
                const int pre = seq[i - 1], cur = seq[i];
                adj[pre].emplace(cur);
                ++inDegree[cur];
            }
        }

        queue<int> q;
        for (int i = 1; i <= n; ++i) { // 遍歷 node 1 ~ n
            if (inDegree[i] == 0) {
                q.emplace(i);
            }
        }

        // bfs
        while (!q.empty()) {
            // 下一個數字的選擇不唯一
            if (q.size() > 1) {
                return false;
            }

            const auto cur = q.front();
            q.pop();

            // 把 cur 給 pop 掉後, 將 cur 的 adjacent vertex 之 in degree - 1
            for (const auto& v : adj[cur]) {
                if (--inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }

        return true;
    }
};
  • time：$O(n+m)$ ➔ bfs() 所需的時間複雜度 $O(V+E)$
    • n 為 nums 的個數(即為 vertex 數)
    • m 為 sequences 的個數(即為 edge 數)
  • space：$O(n+m)$ ➔ 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊