subject ： The original title is link （ secondary ）
label ： chart 、 A topological sort 、 Breadth first search 、 Depth-first search
solution
Time complexity
Spatial complexity
Execution time
Ans 1 (Python)
O ( N )
O ( N )
84ms (12.88%)
Ans 2 (Python)
Ans 3 (Python)
Solution 1 ：
def build_graph(edges):
graph_in = collections.defaultdict(set)
graph_out = collections.defaultdict(set)
for edge in edges:
graph_in[edge[1]].add(edge[0])
graph_out[edge[0]].add(edge[1])
return graph_out, graph_in
def topo(graph_in, graph_out):
count = {} # Node incident edge statistics
queue = [] # The current incident edge is 0 List of nodes
# Count the incident edges of all nodes
for node in graph_in:
count[node] = len(graph_in[node])
for node in graph_out:
if node not in count:
count[node] = 0
queue.append(node)
# A topological sort
order = []
while queue:
node = queue.pop()
order.append(node)
for next in graph_out[node]:
count[next] -= 1
if count[next] == 0:
queue.append(next)
return order
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# Generating adjacency list structure of edges in digraph
graph_in, graph_out = build_graph(prerequisites)
# A topological sort
order = topo(graph_in, graph_out)
order_set = set(order)
for node in graph_in:
if node not in order:
return []
for i in range(numCourses):
if i not in order_set:
order.append(i)
return order
