Course Schedule

Question

Problem description: https://leetcode.com/problems/course-schedule/

Tag

• DFS
• BFS
• Graph
• Topological Sort

Thoughts

• The solution should only return True when all the courses can be finished, which means there should be no cycle for any nodes in the graph.
• The graph might be connected graph or maybe composed by multiple separated graph. The solution should handle both of the situation.
• Since all the courses have to be completed, it is necessary to check all the nodes one by one as the start point in the graph.
• Make use the advantages of DP to avoid repeated calculation.

Code

reference: https://discuss.leetcode.com/topic/13412/python-20-lines-dfs-solution-sharing-with-explanation

def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        def dfs(index):
            if visited[index] == -1:
                return False
            if visited[index] == 1:
                return True
            visited[index] = -1
            for course in graph[index]:
                if not dfs(course):
                    return False
            visited[index] = 1
            return True

        graph = [[] for _ in xrange(numCourses)]
        visited = [0 for _ in xrange(numCourses)]
        for cur_course, pre_course in prerequisites:
            graph[cur_course].append(pre_course)

        for i in xrange(numCourses):
            if not dfs(i):
                return False
        return True