Python Solution with Detailed Explanation


  • 0
    G

    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):
            visiting.add(i)
            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
            visited.add(i)
            visiting.remove(i)
            st.append(i)
            return False
    

Log in to reply
 

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