{"id":7275,"date":"2020-08-22T11:31:08","date_gmt":"2020-08-22T18:31:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7275"},"modified":"2020-08-22T11:31:38","modified_gmt":"2020-08-22T18:31:38","slug":"leetcode-1557-minimum-number-of-vertices-to-reach-all-nodes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1557-minimum-number-of-vertices-to-reach-all-nodes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1557. Minimum Number of Vertices to Reach All Nodes"},"content":{"rendered":"\n

Given a directed acyclic graph<\/strong>, with n<\/code> vertices numbered from 0<\/code> to n-1<\/code>, and an array edges<\/code> where edges[i] = [fromi<\/sub>, toi<\/sub>]<\/code> represents a directed edge from node fromi<\/sub><\/code> to node toi<\/sub><\/code>.<\/p>\n\n\n\n

Find the smallest set of vertices from which all nodes in the graph are reachable<\/em>. It’s guaranteed that a unique solution exists.<\/p>\n\n\n\n

Notice that you can return the vertices in any order.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]\nOutput:<\/strong> [0,3]\nExplanation: <\/strong>It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]\nOutput:<\/strong> [0,2,3]\nExplanation: <\/strong>Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 10^5<\/code><\/li>
  • 1 <= edges.length <= min(10^5, n * (n - 1) \/ 2)<\/code><\/li>
  • edges[i].length == 2<\/code><\/li>
  • 0 <= fromi,<\/sub> toi<\/sub> < n<\/code><\/li>
  • All pairs (fromi<\/sub>, toi<\/sub>)<\/code> are distinct.<\/li><\/ul>\n\n\n\n
    Solution: In degree<\/strong><\/h2>\n\n\n\n
    Nodes with 0 in degree will be the answer.
    Time complexity: O(E+V)
    Space complexity: O(V)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector findSmallestSetOfVertices(int n, vector>& edges) {\n    vector in(n);    \n    for (const auto& e : edges) ++in[e[1]];\n    vector ans;\n    for (int i = 0; i < n; ++i)\n      if (in[i] == 0) ans.push_back(i);\n    return ans;    \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi. Find the smallest set of vertices from which all…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,560,177],"class_list":["post-7275","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-in-degree","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7275"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7275\/revisions"}],"predecessor-version":[{"id":7277,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7275\/revisions\/7277"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}