aboutsummaryrefslogtreecommitdiff
path: root/other/min_num_vertices_node.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_num_vertices_node.cpp')
-rw-r--r--other/min_num_vertices_node.cpp34
1 files changed, 34 insertions, 0 deletions
diff --git a/other/min_num_vertices_node.cpp b/other/min_num_vertices_node.cpp
new file mode 100644
index 0000000..2d53fed
--- /dev/null
+++ b/other/min_num_vertices_node.cpp
@@ -0,0 +1,34 @@
+// 1557. Minimum Number of Vertices to Reach All Nodes
+#include "leetcode.h"
+
+/*
+ * given a directed acyclic graph, with 'n' vertices numbered from 0 to 'n - 1',
+ * and an array 'edges', where 'edges[i] = [fromi, toi]' representes a directed
+ * edge from node 'fromi' to node 'toi'. find the smallest set of vertices from
+ * which all nodes in the graph are reachale. it's guaranteed that a unique
+ * solution exists. notice you cano return the vertices in any order.
+ */
+
+class Solution {
+public:
+ vector<int> findSmallestSetOfVertices(int n, vvd & edges) {
+ vector<int> ans, seen(n);
+ for (auto e : edges)
+ seen[e[1]] = 1;
+ for (int i = 0; i < n; ++i)
+ if (!seen[i])
+ ans.push_back(i);
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1}, {0, 2}, {2, 5}, {3, 4}, {4, 2}};
+ vvd e2 = {{0, 1}, {2, 1}, {3, 1}, {1, 4}, {2, 4}};
+ for (auto i : obj.findSmallestSetOfVertices(6, e1))
+ printf("%d ", i); // expect: 0 3
+ printf("\n");
+ for (auto i : obj.findSmallestSetOfVertices(5, e2))
+ printf("%d ", i); // expect: 0 2 3
+}