2024-06-29
2192. 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.
要记录每个 node 的所有 ancestor
也就是所有可以经过 edge 直接或间接走到这个 node 的 node
没意外就是 DFS 走
原本想要一条路径一路走下去的时候顺便把所有经过的 ancestor 一起带下去
走到底要往回的时候一次塞进去
但是因为是 DAG 一个 node 前面可能很多个 node 可以走到
而且没有一个独一的 root
要分辨有没有走过这条路有点麻烦
而且不同的路走到同一个 node 还是要往下走
所以选择我就抄.jpg
照 answer 一个一个 node 当 root 往下走 一次只推一个
class Solution {
public:
vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
vector<vector<int>> ancestors(n);
vector<vector<int>> adjacent(n);
// construct (sparse) adjacent map
for (const auto& e : edges) {
adjacent[e[0]].push_back(e[1]);
}
// traverse
for (int i = 0; i < n; ++i) {
vector<bool> visit(n, false);
dfs(adjacent, i, i, ancestors, visit);
}
for (int i = 0; i < n; ++i) {
sort(ancestors[i].begin(), ancestors[i].end());
}
return ancestors;
}
private:
void dfs(vector<vector<int>>& adjacent, int root, int cur,
vector<vector<int>>& ancestors, vector<bool>& visit) {
visit[cur] = true;
for (int next : adjacent[cur]) {
if (!visit[next]) {
ancestors[next].push_back(root);
dfs(adjacent, root, next, ancestors, visit);
}
}
}
};