🎨Now live: Try our Free AI Image Generation Feature

Intuition
In a Directed Acyclic Graph (DAG), nodes have directed edges that indicate a relationship from one node to another. To find the ancestors of each node, we need to determine which nodes can reach a given node via directed paths. The problem requires identifying all such ancestors and returning them sorted.
Approach
- Graph Representation: Use an adjacency list to represent the graph. Each node points to a set of nodes it can directly reach.
- Depth-First Search (DFS): Implement a DFS function to explore each node and find all reachable nodes, marking them as ancestors. This involves recursively visiting nodes and adding the current node to the list of ancestors for each of its descendants.
- Traversal and Collection: For each node, initiate a DFS. Use a visited array to avoid revisiting nodes within the same DFS call, preventing cycles and redundant work.
- Sorting: After all ancestors are found for each node, sort the ancestor lists to meet the problem's requirement.
Complexity
- Time Complexity: O(n^2), where n is the number of nodes. Each node's DFS can visit all other nodes in the worst case.
- Space Complexity: O(n^2), required for the adjacency list, ancestor list, and visited array.
Detailed Explanation
var map = Array.from({ length: n }, () => new Set());
var res = Array.from({ length: n }, () => []);
var visited = new Uint8Array(n);
map
: An array of sets where each index corresponds to a node and contains a set of nodes it can directly reach.res
: An array of arrays that will hold the list of ancestors for each node.visited
: A boolean array used to keep track of visited nodes during DFS to avoid revisits.
var dfs = (v, p) => {
visited[v] = 1;
if (v !== p) res[v].push(p);
for (var x of map[v]) if (!visited[x]) dfs(x, p);
};
dfs
: A depth-first search function that traverses the graph from nodev
, marking ancestors inres
. Ifv
is not the starting nodep
,p
is added as an ancestor ofv
.
edges.forEach(([u, v]) => map[u].add(v));
- Populate the
map
with edges where each edge[u, v]
indicates a direct connection from nodeu
to nodev
.
for (let i = 0; i < n; ++i) visited.fill(0), dfs(i, i);
- For each node
i
, reset thevisited
array and perform a DFS starting fromi
. This finds all ancestors ofi
.
return res;
- Return the
res
array containing sorted lists of ancestors for each node.
Code
C++
class Solution {
public:
vector> getAncestors(int n, vector>& edges) {
vector> map(n);
vector> res(n);
vector visited(n);
function dfs = [&](int v, int p) {
visited[v] = true;
if (v != p) res[v].push_back(p);
for (int x : map[v]) {
if (!visited[x]) dfs(x, p);
}
};
for (const auto& edge : edges) {
map[edge[0]].insert(edge[1]);
}
for (int i = 0; i < n; ++i) {
fill(visited.begin(), visited.end(), false);
dfs(i, i);
}
return res;
}
};
Python
class Solution:
def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
map = [set() for _ in range(n)]
res = [[] for _ in range(n)]
visited = [False] * n
def dfs(v: int, p: int):
visited[v] = True
if v != p:
res[v].append(p)
for x in map[v]:
if not visited[x]:
dfs(x, p)
for u, v in edges:
map[u].add(v)
for i in range(n):
visited = [False] * n
dfs(i, i)
return res
Java
class Solution {
public List> getAncestors(int n, int[][] edges) {
List> map = new ArrayList<>();
List> res = new ArrayList<>();
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
map.add(new HashSet<>());
res.add(new ArrayList<>());
}
for (int[] edge : edges) {
map.get(edge[0]).add(edge[1]);
}
for (int i = 0; i < n; i++) {
Arrays.fill(visited, false);
dfs(i, i, map, res, visited);
}
return res;
}
private void dfs(int v, int p, List> map, List> res, boolean[] visited) {
visited[v] = true;
if (v != p) res.get(v).add(p);
for (int x : map.get(v)) {
if (!visited[x]) {
dfs(x, p, map, res, visited);
}
}
}
}
JavaScript
/**
* @param {number} n
* @param {number[][]} edges
* @return {number[][]}
*/
var getAncestors = function (n, edges) {
var map = Array.from({ length: n }, () => new Set());
var res = Array.from({ length: n }, () => []);
var visited = new Uint8Array(n);
var dfs = (v, p) => {
visited[v] = 1;
if (v !== p) res[v].push(p);
for (var x of map[v]) if (!visited[x]) dfs(x, p);
};
edges.forEach(([u, v]) => map[u].add(v));
for (let i = 0; i < n; ++i) visited.fill(0), dfs(i, i);
return res;
};