发表于 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]

• LC 题目链接