Python Solution with Detailed Explanation

• Solution

Course Schedule II https://leetcode.com/problems/course-schedule-ii/

Topological Sort using DFS Solution: O(V+E)

• Topological sort is reverse post-order DFS.
• We create a graph given the input constraints. Then we run topo-sort.
• We combine the code to detect a cycle and perform topo-sort. If there is a cycle, then we return an empty list.
``````class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
g = {}
for i in range(numCourses):
g[i] = []
for pre in prerequisites:
u, v = pre[1], pre[0]
g[u].append(v)
order = self.topo_sort(g, numCourses)
return order

def topo_sort(self, g, n):
visiting, visited, st = set([]), set([]), []
for i in range(n):
if i not in visited:
if self.dfs(g,i,st,visiting, visited):
return []
st.reverse()
return st

def dfs(self, g, i, st, visiting, visited):
for nbr in g[i]:
if nbr in visiting:
return True
elif nbr not in visited:
if self.dfs(g, nbr, st, visiting, visited):
return True