題目描述: 給定一個有向無環圖(DAG),有 n 個節點和若干邊 edges[i] = [from, to]。對每個節點,找出所有祖先節點(能到達該節點的所有節點),按升序排列。
解題思路: 方法一:對每個節點做反向 DFS/BFS。
方法二(更高效):從每個節點出發做 DFS,標記所有可達節點為它的後代。
方法三:拓撲排序 + 集合合併。按拓撲序處理,每個節點的祖先 = 直接父節點的祖先聯集 + 直接父節點。
時間複雜度: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)),但需要額外排序每個祖先列表。