Dare2Solve
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.
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 node v
, marking ancestors in res
. If v
is not the starting node p
, p
is added as an ancestor of v
.edges.forEach(([u, v]) => map[u].add(v));
map
with edges where each edge [u, v]
indicates a direct connection from node u
to node v
.for (let i = 0; i < n; ++i) visited.fill(0), dfs(i, i);
i
, reset the visited
array and perform a DFS starting from i
. This finds all ancestors of i
.return res;
res
array containing sorted lists of ancestors for each node.class Solution {
public:
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
vector<set<int>> map(n);
vector<vector<int>> res(n);
vector<bool> visited(n);
function<void(int, int)> 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;
}
};
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
class Solution {
public List<List<Integer>> getAncestors(int n, int[][] edges) {
List<Set<Integer>> map = new ArrayList<>();
List<List<Integer>> 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<Set<Integer>> map, List<List<Integer>> 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);
}
}
}
}
/**
* @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;
};