Python Solution with Detailed Explanation

  • 0


    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]
            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 []
            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
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.