🔗 🟡 2192. All Ancestors of a Node in a Directed Acyclic Graph 1788

tags: `Biweekly Contest 73` `圖(Graph)` `DFS` `BFS` `拓撲排序(Topological Sort)`

題意

給定一個正整數 $n$ ，代表有向無環圖 (DAG) 中節點的數量。這些節點的編號從 $0$ 到 $n-1$ 。

另給定一個二維整數陣列 $\text{edges}$ ，其中 $\text{edges}[i] = [\text{from}_i, \text{to}_i]$ 表示圖中存在一條從 $\text{from}_i$ 到 $\text{to}_i$ 的單向邊。

返回一個二維列表 $\text{answer}$ ，其中 $\text{answer}[i]$ 是第 $i$ 個節點的祖先列表，且需要按照升序排序。

思路：DFS

雖然答案要從子節點的角度來尋找所有祖先，但不妨換個角度思考，從父節點的角度來尋找所有子節點，這樣就可以使用 DFS 或 BFS 來解決。

對於每個節點 $st$ ，我們可以使用 DFS 來尋找所有 $st$ 的子節點，並將 $st$ 加入到子節點的祖先列表中。

由於答案要求按照升序排列，因此我們可以依照從 $0$ 到 $n-1$ 的順序，來進行 DFS。

複雜度分析

時間複雜度： $O(n(n + m))$ $O (n (n + m))$ ，其中 $m$ $m$ 為邊的數量。
- 每個節點都需要進行 DFS，DFS 的時間複雜度為 $O(n + m)$ 。
空間複雜度： $O(n + m)$ ，需要額外空間來存儲圖的鄰接表。

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)

        def dfs(st:int, u: int) -> None:
            for v in g[u]:
                if not visited[v]:
                    visited[v] = True
                    ans[v].append(st)
                    dfs(st, v)

        ans = [[] for _ in range(n)]
        for st in range(n):
            visited = [False] * n
            dfs(st, st)
        return ans

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
        }

        vector<vector<int>> ans(n);
        vector<bool> visited(n, false);
        
        function<void(int, int)> dfs = [&](int st, int u) {
            for (int v : g[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    ans[v].push_back(st);
                    dfs(st, v);
                }
            }
        };

        for (int st = 0; st < n; ++st) {
            fill(visited.begin(), visited.end(), false);
            dfs(st, st);
        }
        return ans;
    }
};