2192. All Ancestors of a Node in a Directed Acyclic Graph

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 2192

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        def bfs(s: int):
            q = deque([s])
            vis = {s}
            while q:
                i = q.popleft()
                for j in g[i]:
                    if j not in vis:
                        vis.add(j)
                        q.append(j)
                        res[j].append(s)

        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
        res = [[] for _ in range(n)]
        for i in range(n):
            bfs(i)
        return res