MediumRating 1788
2192. All Ancestors of a Node in a Directed Acyclic Graph
depth-first-searchbreadth-first-searchgraphtopological-sort
解題說明
All Ancestors of a Node in a Directed Acyclic Graph
題目描述： 給定一個有向無環圖（DAG），有 n 個節點和若干邊 edges[i] = [from, to]。對每個節點，找出所有祖先節點（能到達該節點的所有節點），按升序排列。
解題思路： 方法一：對每個節點做反向 DFS/BFS。
方法二（更高效）：從每個節點出發做 DFS，標記所有可達節點為它的後代。
- 對每個節點 u（從 0 到 n-1），做 DFS 遍歷其所有後代。
- 對 DFS 過程中到達的每個節點 v，將 u 加入 v 的祖先列表。
- 由於我們按 u = 0, 1, 2, ... 的順序遍歷，每個祖先列表自然已按升序排列。
方法三：拓撲排序 + 集合合併。按拓撲序處理，每個節點的祖先 = 直接父節點的祖先聯集 + 直接父節點。
C++ 解法
複雜度分析
時間複雜度：O(n * (n + m)) — 對每個節點做一次 BFS/DFS，每次 O(n + m)。
空間複雜度：O(n^2 + m) — 祖先列表在最壞情況下總共 O(n^2) 個元素，鄰接表 O(m)。
虛擬碼
1. Build adjacency list from edges. 2. For each node u = 0 to n-1: a. BFS/DFS from u to find all reachable nodes. b. For each reachable node v: add u to ancestors[v]. 3. Return ancestors (lists are already sorted since u iterates in order).
其他解法
-
拓撲排序 + 位元集合：按拓撲序處理節點，每個節點的祖先集合 = 所有直接父節點的祖先集合的聯集 + 直接父節點。使用 bitset 加速集合合併，O(n^2 / 64) 空間和時間。
-
反向圖 DFS：反轉所有邊的方向，對每個節點做 DFS 找所有可達節點（即原圖中的祖先）。時間複雜度相同 O(n * (n + m))，但需要額外排序每個祖先列表。
延伸思考
- 若圖可能有環（不是 DAG），如何先用 SCC（強連通分量）縮點後再求祖先？
- 若只需要查詢特定 k 個節點的祖先（而非所有節點），如何優化？
- 若邊是帶權的，如何找出每個節點的所有祖先及到達的最短距離？