Course Schedule II

Problem: Course Schedule II

We just consider course prerequisites as edges in a graph and do topological sort and we can get our answer.

Code in Python:

from collections import deque

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        out = [[] for _ in xrange(numCourses)]
        in_degree = [0] * numCourses
        for prerequisite in prerequisites:
            out[prerequisite[1]].append(prerequisite[0])
            in_degree[prerequisite[0]] += 1
        queue = deque([])
        for i in xrange(numCourses):
            if in_degree[i] == 0: queue.append(i)
        ans = []
        while queue:
            x = queue.popleft()
            ans.append(x)
            for course in out[x]:
                if in_degree[course] == 1: queue.append(course)
                else: in_degree[course] -= 1
        return ans if len(ans) == numCourses else []