JZX轻语：简
LeetCode每日一题(20240404) - 有向无环图中一个节点的所有祖先
发表于2024年04月04日
思路比较直观，就是利用拓扑排序的想法，每次寻找入度为0的节点，然后更新子节点的祖先数据和入度即可，直至所有的节点都遍历完毕(因为没有环，最终所有的节点都会入度为0)。
寻找入度为0的节点的过程可以利用队列优化下，使用队列维护当前入度为0的节点，当处理子节点的时候若子节点的入度也变为0了，则将该子节点推入队列即可。
from collections import deque
class Solution:
def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
adjList = [[] for _ in range(n)]
result = [set() for _ in range(n)]
in_ = [0] * n
for edge in edges:
u, v = edge
adjList[u].append(v)
in_[v] += 1
zero_in_degree = deque(node for node in range(n) if in_[node] == 0)
while zero_in_degree:
node = zero_in_degree.popleft() # type: int
for child in adjList[node]:
in_[child] -= 1
result[child].add(node)
result[child] |= result[node]
if in_[child] == 0:
zero_in_degree.append(child)
return [sorted(list(item)) for item in result]