※ 引述《smart0eddie (smart0eddie)》之銘言：
: 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);
: }
: }
: }
: };
思路:
我本來想說紀錄所有子節點的父節點
就record = {}
record[kid].append(ancestor)
然後再把父節點的父節點加上去
後來發現會重複 所以改用set()紀錄
但改用set()又有排序問題
果斷看解答 姆咪
Python Code:
class Solution:
def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
def dfs(ancestor,kid):
if not (result[kid] and result[kid][-1] == ancestor):
if kid != ancestor:
result[kid].append(ancestor)
for grand_child in record[kid]:
dfs(ancestor,grand_child)
record = defaultdict(list)
for edge in edges:
record[edge[0]].append(edge[1])
result = [[] for _ in range(n)]
for i in range(n):
dfs(i,i)
return result