diff options
-rw-r--r-- | ancestors_node_acyclic_graph.cpp | 58 | ||||
-rw-r--r-- | ancestors_node_acyclic_graph.py | 71 |
2 files changed, 129 insertions, 0 deletions
diff --git a/ancestors_node_acyclic_graph.cpp b/ancestors_node_acyclic_graph.cpp new file mode 100644 index 0000000..69917c5 --- /dev/null +++ b/ancestors_node_acyclic_graph.cpp @@ -0,0 +1,58 @@ +// 2192. All Ancestors of a Node in a Directed Acyclic Graph +#include "leetcode.h" + +/* + * 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' inclusively. + * you are also given a 2d integer array 'edges' where 'edges[i] = [fromi, toi]' + * denotes that there is a unidirectional edge from 'fromi' to 'toi' in the + * graph. return a list 'answer' where 'answer[i]' is the list of ancestors of + * the i'th node, sorted in ascending order. a node 'u' is an ancestor of + * another node 'v' if 'u' can reach 'v' via a set of edges. + */ + +class Solution { +private: + void dfs(int x, int curr, vector<vector<int>> &res, + vector<vector<int>> &direct_child) { + for (auto &i : direct_child[curr]) + if (!res[i].size() || res[i].back() != x) { + res[i].push_back(x); + dfs(x, i, res, direct_child); + } + } + +public: + vector<vector<int>> getAncestors(int n, vector<vector<int>> &edges) { + vector<vector<int>> ans(n), direct_child(n); + for (auto &i : edges) + direct_child[i[0]].push_back(i[1]); + for (int i = 0; i < n; i++) + dfs(i, i, ans, direct_child); + return ans; + } +}; + +int main() { + Solution obj; + vvd(int) e1 = {{0, 3}, {0, 4}, {1, 3}, {2, 4}, {2, 7}, + {3, 5}, {3, 6}, {3, 7}, {4, 6}}; + vvd(int) e2 = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, + {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}; + vvd(int) ga1 = obj.getAncestors(8, e1), ga2 = obj.getAncestors(5, e2); + for (int i = 0; i < ga1.size(); i++) { + for (int j = 0; j < ga1[0].size(); j++) + printf("%d ", + ga1[i][j]); // expect: + // [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < ga2.size(); i++) { + for (int j = 0; j < ga2[0].size(); j++) + printf("%d ", + ga2[i][j]); // expect: [[],[0],[0,1],[0,1,2],[0,1,2,3]] + printf("\n"); + } + printf("\n"); +} diff --git a/ancestors_node_acyclic_graph.py b/ancestors_node_acyclic_graph.py new file mode 100644 index 0000000..b592e12 --- /dev/null +++ b/ancestors_node_acyclic_graph.py @@ -0,0 +1,71 @@ +# 2192. All Ancestors of a Node in a Directed Acyclic Graph +from collections import defaultdict + +""" +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' inclusively. +you are also given a 2d integer array 'edges' where 'edges[i] = [fromi, toi]' +denotes that there is a unidirectional edge from 'fromi' to 'toi' in the +graph. return a list 'answer' where 'answer[i]' is the list of ancestors of +the i'th node, sorted in ascending order. a node 'u' is an ancestor of +another node 'v' if 'u' can reach 'v' via a set of edges. +""" + + +class Solution(object): + def getAncestors(self, n, edges): + """ + :type n: int + :type edges: List[List[int]] + :rtype: List[List[int]] + """ + direct_child = defaultdict(list) + ans = [[] for _ in range(n)] + for x,y in edges: + direct_child[x].append(y) + def dfs(x, curr): + for i in direct_child[curr]: + if ans[i] ans and ans[i][-1] == x: + continue + ans[i].append(x) + dfs(x, i) + for i in range(n): + dfs(i, i) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.getAncestors( + n=8, + edgeList=[ + [0, 3], + [0, 4], + [1, 3], + [2, 4], + [2, 7], + [3, 5], + [3, 6], + [3, 7], + [4, 6], + ], + ) + ) + print( + obj.getAncestors( + n=5, + edgeList=[ + [0, 1], + [0, 2], + [0, 3], + [0, 4], + [1, 2], + [1, 3], + [1, 4], + [2, 3], + [2, 4], + [3, 4], + ], + ) + ) |