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 個節點的祖先(而非所有節點),如何優化?
- 若邊是帶權的,如何找出每個節點的所有祖先及到達的最短距離?