2192. All Ancestors of a Node in a Directed Acyclic Graph LeetCode Solution
In this guide, you will get 2192. All Ancestors of a Node in a Directed Acyclic Graph LeetCode Solution with the best time and space complexity. The solution to All Ancestors of a Node in a Directed Acyclic Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of All Ancestors of a Node in a Directed Acyclic Graph
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 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 ith 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.
Example 1:
Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
– Nodes 0, 1, and 2 do not have any ancestors.
– Node 3 has two ancestors 0 and 1.
– Node 4 has two ancestors 0 and 2.
– Node 5 has three ancestors 0, 1, and 3.
– Node 6 has five ancestors 0, 1, 2, 3, and 4.
– Node 7 has four ancestors 0, 1, 2, and 3.
Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
– Node 0 does not have any ancestor.
– Node 1 has one ancestor 0.
– Node 2 has two ancestors 0 and 1.
– Node 3 has three ancestors 0, 1, and 2.
– Node 4 has four ancestors 0, 1, 2, and 3.
Constraints:
1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n – 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n – 1
fromi != toi
There are no duplicate edges.
The graph is directed and acyclic.
Complexity Analysis
Time Complexity: O(|\texttt{edges}|)
Space Complexity: O(|\texttt{edges}|)
2192. All Ancestors of a Node in a Directed Acyclic Graph LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
vector<vector<int>> ans(n);
vector<vector<int>> graph(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].push_back(v);
}
for (int i = 0; i < n; ++i)
dfs(graph, i, i, vector<bool>(n), ans);
return ans;
}
private:
void dfs(const vector<vector<int>>& graph, int u, int ancestor,
vector<bool>&& seen, vector<vector<int>>& ans) {
seen[u] = true;
for (const int v : graph[u]) {
if (seen[v])
continue;
ans[v].push_back(ancestor);
dfs(graph, v, ancestor, std::move(seen), ans);
}
}
}; /* code provided by PROGIEZ */
2192. All Ancestors of a Node in a Directed Acyclic Graph LeetCode Solution in Java
class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; ++i) {
ans.add(new ArrayList<>());
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(v);
}
for (int i = 0; i < n; ++i)
dfs(graph, i, i, new boolean[n], ans);
return ans;
}
private void dfs(List<Integer>[] graph, int u, int ancestor, boolean[] seen,
List<List<Integer>> ans) {
seen[u] = true;
for (final int v : graph[u]) {
if (seen[v])
continue;
ans.get(v).add(ancestor);
dfs(graph, v, ancestor, seen, ans);
}
}
} // code provided by PROGIEZ
2192. All Ancestors of a Node in a Directed Acyclic Graph LeetCode Solution in Python
class Solution:
def getAncestors(self, n: int, edges: list[list[int]]) -> list[list[int]]:
ans = [[] for _ in range(n)]
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
def dfs(u: int, ancestor: int, seen: set[int]) -> None:
seen.add(u)
for v in graph[u]:
if v in seen:
continue
ans[v].append(ancestor)
dfs(v, ancestor, seen)
for i in range(n):
dfs(i, i, set())
return ans # code by PROGIEZ
