※ 引述《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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.138.195 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719676052.A.9DD.html