推 SecondRun: 別捲了 06/29 13:30
→ Rushia: 這題就拓樸排序 對每個點DFS然後走過的忽略 06/29 15:32
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);
}
}
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719638358.A.BD6.html