Back to course home
0% completed
Vote For New Content
the proper solution
Mohammed Dh Abbas
Jun 8, 2024
The official solution is bad and disagree with how it was done. how uses queue.remove() ???. that's O(operation)
This is a the proper solution to the question
from collections import deque class Solution: def __init__(self): self.orders = [] # this is a backtracking / permutatinal + topological solution def topo(self, path, seen): # base case if len(path) == len(self.graph): self.orders.append(path[:]) return # instead of using queue to procee the next 0 node we recurse and loop to find the 0 node for node in self.graph: if self.indegree[node] == 0 and not seen.get(node): seen[node] = True path.append(node) for nex_node in self.graph[node]: self.indegree[nex_node] -= 1 self.topo(path, seen) # undo the change as the values gets used when one path completes for nex_node in self.graph[node]: self.indegree[nex_node] += 1 seen[node] = False path.pop() def printOrders(self, tasks, prerequisites): # edge cases if tasks == 0: return self.orders elif tasks == 1: self.orders.append([0]) return self.orders # build graph and indegree self.graph = {} self.indegree = {} for i in range(tasks): self.graph[i] = [] self.indegree[i] = 0 for before, after in prerequisites: self.graph[before].append(after) self.indegree[after] += 1 self.topo([], {}) return self.orders
0
0
Comments
Comments
On this page