{"id":9570,"date":"2022-03-11T23:14:40","date_gmt":"2022-03-12T07:14:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9570"},"modified":"2022-03-11T23:19:35","modified_gmt":"2022-03-12T07:19:35","slug":"leetcode-2192-all-ancestors-of-a-node-in-a-directed-acyclic-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2192-all-ancestors-of-a-node-in-a-directed-acyclic-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph"},"content":{"rendered":"\n

You are given a positive integer n<\/code> representing the number of nodes of a Directed Acyclic Graph<\/strong> (DAG). The nodes are numbered from 0<\/code> to n - 1<\/code> (inclusive<\/strong>).<\/p>\n\n\n\n

You are also given a 2D integer array edges<\/code>, where edges[i] = [fromi<\/sub>, toi<\/sub>]<\/code> denotes that there is a unidirectional<\/strong> edge from fromi<\/sub><\/code> to toi<\/sub><\/code> in the graph.<\/p>\n\n\n\n

Return a list<\/em> answer<\/code>, where <\/em>answer[i]<\/code> is the list of ancestors<\/strong> of the<\/em> ith<\/sup><\/code> node, sorted in ascending order<\/strong><\/em>.<\/p>\n\n\n\n

A node u<\/code> is an ancestor<\/strong> of another node v<\/code> if u<\/code> can reach v<\/code> via a set of edges.<\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\nOutput:<\/strong> [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]\nExplanation:<\/strong>\nThe above diagram represents the input graph.\n- Nodes 0, 1, and 2 do not have any ancestors.\n- Node 3 has two ancestors 0 and 1.\n- Node 4 has two ancestors 0 and 2.\n- Node 5 has three ancestors 0, 1, and 3.\n- Node 6 has five ancestors 0, 1, 2, 3, and 4.\n- Node 7 has four ancestors 0, 1, 2, and 3.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]\nOutput:<\/strong> [[],[0],[0,1],[0,1,2],[0,1,2,3]]\nExplanation:<\/strong>\nThe above diagram represents the input graph.\n- Node 0 does not have any ancestor.\n- Node 1 has one ancestor 0.\n- Node 2 has two ancestors 0 and 1.\n- Node 3 has three ancestors 0, 1, and 2.\n- Node 4 has four ancestors 0, 1, 2, and 3.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= 1000<\/code><\/li>
  • 0 <= edges.length <= min(2000, n * (n - 1) \/ 2)<\/code><\/li>
  • edges[i].length == 2<\/code><\/li>
  • 0 <= fromi<\/sub>, toi<\/sub> <= n - 1<\/code><\/li>
  • fromi<\/sub> != toi<\/sub><\/code><\/li>
  • There are no duplicate edges.<\/li>
  • The graph is directed<\/strong> and acyclic<\/strong>.<\/li><\/ul>\n\n\n\n
    Solution: DFS<\/strong><\/h2>\n\n\n\n
    For each source node S, add it to all its reachable nodes by traversing the entire graph.
    In one pass, only traverse each child node at most once.<\/p>\n\n\n\n
    Time complexity: O(VE)
    Space complexity: (V+E)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector> getAncestors(int n, vector>& edges) {\n    vector> ans(n);\n    vector> g(n);\n    for (const auto& e : edges)\n      g[e[0]].push_back(e[1]);    \n    \n    function dfs = [&](int s, int u) -> void {\n      for (int v : g[u]) {\n        if (ans[v].empty() || ans[v].back() != s) {\n          ans[v].push_back(s);\n          dfs(s, v);\n        }\n      }\n    };\n    \n    for (int i = 0; i < n; ++i)\n      dfs(i, i);  \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n – 1 (inclusive). You are also given…<\/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":[33,77,177],"class_list":["post-9570","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dfs","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9570","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=9570"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9570\/revisions"}],"predecessor-version":[{"id":9575,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9570\/revisions\/9575"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}