444 solved.

liuyubobobo · liuyubobobo · commit ed1a1db33f2a · 2022-07-22T12:09:23.000-07:00
diff --git a/0001-0500/0444-Sequence-Reconstruction/cpp-0444/CMakeLists.txt b/0001-0500/0444-Sequence-Reconstruction/cpp-0444/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0444)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0444 main.cpp)
diff --git a/0001-0500/0444-Sequence-Reconstruction/cpp-0444/main.cpp b/0001-0500/0444-Sequence-Reconstruction/cpp-0444/main.cpp
@@ -0,0 +1,57 @@
+/// Source : https://leetcode.com/problems/sequence-reconstruction/
+/// Author : liuyubobobo
+/// Time   : 2022-07-22
+
+#include <iostream>
+#include <vector>
+#include <queue>
+
+using namespace std;
+
+
+/// Topological Sort
+/// Time Complexity: O(n + m)
+/// Space Complexity: O(n + m)
+class Solution {
+public:
+    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
+
+        int n = nums.size();
+
+        vector<vector<int>> g(n);
+        for(const vector<int>& seq: sequences){
+            for(int i = 1; i < seq.size(); i ++){
+                int a = seq[i - 1] - 1, b = seq[i] - 1;
+                g[a].push_back(b);
+            }
+        }
+
+        vector<int> indegrees(n, 0);
+        for(int u = 0; u < n; u ++)
+            for(int v: g[u]) indegrees[v] ++;
+
+        queue<int> q;
+        for(int u = 0; u < n; u ++)
+            if(indegrees[u] == 0) q.push(u);
+
+        vector<int> res;
+        while(!q.empty()){
+            if(q.size() > 1) return false;
+
+            int u = q.front(); q.pop();
+            res.push_back(u + 1);
+            for(int v: g[u]){
+                indegrees[v] --;
+                if(indegrees[v] == 0) q.push(v);
+            }
+        }
+
+        return res == nums;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -476,7 +476,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 441 | [Arranging Coins](https://leetcode.com/problems/arranging-coins/) | [solution](https://leetcode.com/problems/arranging-coins/solution/) | [C++](0001-0500/0441-Arranging-Coins/cpp-0441/) | | |
 | 442 | [Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/) | [solution](https://leetcode.com/problems/find-all-duplicates-in-an-array/solution/) | [C++](0001-0500/0442-Find-All-Duplicates-in-an-Array/cpp-0442/) | | |
 | 443 | [String Compression](https://leetcode.com/problems/string-compression/description/) | | [C++](0001-0500/0443-String-Compression/cpp-0443/) | | |
-| | | | | | |
+| 444 | [Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/) | [无] | [C++](0001-0500/0444-Sequence-Reconstruction/cpp-0444/) | | |
 | 445 | [Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/) | [无] | [C++](0001-0500/0445-Add-Two-Numbers-II/cpp-0445/) | | |
 | 446 | [Arithmetic Slices II - Subsequence](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/) | [solution](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/solution/) | [C++](0001-0500/0446-Arithmetic-Slices-II-Subsequence/cpp-0446/) | | |
 | 447 | [Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/description/) | [无] | [C++](0001-0500/0447-Number-of-Boomerangs/cpp-0447/) | [Java](0001-0500/0447-Number-of-Boomerangs/java-0447/src/) | |
