LC 0207 0210 [M] [M] Course Schedule I, II - ALawliet/algorithms GitHub Wiki
we want all nodes going from left to right, assuming there is no cycle
topsort to collect all nodes in increasing departure time order in linear time with Kahn's indegree
pay attention to the ordering e.g. [0,1] means you gotta take course 1 before course 0 so you either build indegrees with 0<-1 (a<-b) and reverse the toposort at the end or do 1->0 (b->a)
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
order = []
adj = {i:[] for i in range(numCourses)}
indeg = {i:0 for i in range(numCourses)}
for nxt, pre in prerequisites:
adj[pre].append(nxt)
indeg[nxt] += 1
Q = deque([i for i in indeg if indeg[i] == 0])
while Q:
u = Q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
Q.append(v)
return len(order) == numCourses # Course Schedule
return order if len(order) == numCourses else [] # Course Schedule II