diff options
Diffstat (limited to 'min_num_vertices_node.cpp')
-rw-r--r-- | min_num_vertices_node.cpp | 34 |
1 files changed, 0 insertions, 34 deletions
diff --git a/min_num_vertices_node.cpp b/min_num_vertices_node.cpp deleted file mode 100644 index 2d53fed..0000000 --- a/min_num_vertices_node.cpp +++ /dev/null @@ -1,34 +0,0 @@ -// 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 -} |