圖論:找出每個節點的祖先 All Ancestors of a Node in a DAG_Leetcode #2192

Ryan Miglinczy on Unsplash

題目敘述 All Ancestors of a Node in a Directed Acyclic Graph

給定一個有向無環圖，請找出每個點的祖先，以陣列的形式返回答案。

測試範例

Example 1:

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

約束條件

Constraints:

• 1 <= n <= 1000

節點總數目介於1~1000之間。

• 0 <= edges.length <= min(2000, n * (n - 1) / 2)

邊的數目介於1~2000之間。

• edges[i].length == 2

edge陣列內容是(起點, 終點)pair

• 0 <= fromi, toi <= n - 1

節點的索引介於0 ~ n-1之間。

• fromi != toi

起點保證和終點相異。

• There are no duplicate edges.

保證不會有重複邊。

• The graph is directed and acyclic.

輸入一定是有向的無環圖。

演算法 建立長輩晚輩關係

先透過輸入的每條邊的起點終點資訊，建立長輩晚輩關係。

接著拜訪整張圖，透過長輩晚輩關係，標定出每個節點的祖先。

程式碼 建立長輩晚輩關係

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        
        children = defaultdict(set)

        ancestor = [ [] for _ in range(n) ]

        for src, dst in edges:
            children[src].add(dst)

        def dfs(senior, node):

            for kid in children[node]:
                if ancestor[kid] and ancestor[kid][-1] == senior:
                    continue

                ancestor[kid].append(senior)
                dfs(senior, kid)
        
            return
        #------------------------------------

        for nodeIdx in range(n):
            dfs(senior=nodeIdx, node=nodeIdx)
        
        return ancestor

複雜度分析

時間複雜度: O(n^2 + E)

建立長輩晚輩關係耗時O(E)

迭代每個節點耗時O(n)，每次迭代需拜訪整張圖耗時O(n)，整體耗時O(n^2)

空間複雜度:O(n)

建立長輩晚輩關係的表格需要O(n)空間。

DFS run-time遞迴最大深度亦為O(n)。

Reference

[1] All Ancestors of a Node in a Directed Acyclic Graph - LeetCode