題目敘述 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
