Moment For Technology

Leetcode 2192. All rooted of a Node in a Directed Acyclic Graph (Python)

Posted on May 28, 2023, 2:35 a.m. by Brian Tanner
Category: The back-end Tag: The back-end algorithm leetcode

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details


This is the third question in the Biweekly Contest 73, which examines the traversal and BFS of directed acyclic graphs on Medium.


You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Example 1:

Input: n = 8, edgeList = [[0, 3], [0, 4], [1, 3], [2, 4], [2, 7], [3, 5], [3], [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.Copy the code


  • 1 = n = 1000
  • 0 = edges.length = min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 = fromi, toi = n - 1
  • fromi ! = toi
  • There are no duplicate edges.
  • The graph is directed and acyclic.


A positive integer n is given to represent the number of nodes in a directed acyclic graph (DAG). Nodes are numbered from 0 to N-1. In addition, a two-dimensional integer array is given. Edges [I] = [fromi, toi] indicates that there is a one-way edge from Fromi to TOi in the graph.

Return a list answer, where answer[I] is the ancestor list of the ith node, requiring that the ancestor list be sorted in ascending order. If u can reach V through one edge, then node U is the ancestor of another node V.

First we use the ancestor definition above to find the dictionary D by iterating over the elements of the edges. D represents {child node :[initial ancestor list]}. Then we iterate over each index I from 0 to n-1, indicating that we are looking for the ancestor of the index I node. If I does not exist in D, it indicates that there is no ancestor. Therefore, you can directly append an empty list to the result list, and then go through the next cycle to find the ancestor of the next node. If I is in D, we use BFS to traverse all the ancestors it can find, put all the ancestors into the set piece, sort them in ascending order, append them to result, and continue the ancestor search of the next node. Return result after the ancestors of all nodes are found.

The time complexity is O(N^2), the space complexity is O(N^2).

In fact, this problem can also be solved with DFS, so you can try it, but I won't go into it here.


class Solution(object):
    def getAncestors(self, n, edges):
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[List[int]]
        d = {}
        for a,b in edges:
            d[b] = d.get(b, []) + [a]
        result = []
        for i in range(n):
            if i not in d:
            ancestors = set(d[i])
            stack = copy.deepcopy(d[i])
            while stack:
                node = stack.pop(0)
                if node in d:
                    for n in d[node]:
                        if n not in ancestors:
        return result
Copy the code

The results

80/80 Test cases passed. Status: Accepted Runtime: 1827 MS Memory Usage: 28.6 MBCopy the code

The original link

Your support is my biggest motivation

About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.