aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ancestors_node_acyclic_graph.cpp58
-rw-r--r--ancestors_node_acyclic_graph.py71
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],
+ ],
+ )
+ )