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

preface

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

describe

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

Note:

  • 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.

parsing

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.

answer

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:
                result.append([])
                continue
            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:
                            ancestors.add(n)
                            stack.append(n)
            result.append(sorted(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

Leetcode.com/contest/biw…

Your support is my biggest motivation