Course Schedule

Problem: Course Schedule

The general idea is to use breadth-first-search for topological sort on the graph. To simplify the solution, we do topological sort from the end of the spanning tree of the graph and try to find its parent in spanning tree. If we spanned a partial tree and some of the graph cannot be spanned, we can judge that there's a cycle in the graph.

Code in Python:

from collections import deque

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        ind = [[] for _ in xrange(numCourses)]
        oud = [0] * numCourses
        for r in prerequisites:
            oud[r[0]] += 1
            ind[r[1]].append(r[0])

        queue = deque()
        for i in xrange(numCourses):
            if not oud[i]:
                queue.append(i)

        k = 0    
        while queue:
            cur = queue.popleft()
            k += 1
            for prev in ind[cur]:
                oud[prev] -= 1
                if not oud[prev]:
                    queue.append(prev)

        return k == numCourses