210 Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

N^2 Solution

One way of performing a topological sort if first by finding an empty list. This implies it has no dependances - so it can be added into your list. Then we iterate through the list again, and remove all instances of this course. Recursively performing the same proceedure on this list will eventually yeild the complete topological ordering. In the end, the graph should be empty as an indication that all the courses were successfully ordered. Otherwise there must have been some cyclic dependancies.

import collections

class Solution:
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        # create directed graph
        g = {course: set() for course in range(0, numCourses)}
        for pair in prerequisites:
            g[pair[0]].add(pair[1])

        sol = []
        def topological_sort():
            for course, dependances in g.items():
                if len(dependances) is 0:
                    sol.append(course)
                    del g[course]
                    for _, dependances2 in g.items():
                        if dependances2.__contains__(course):
                            dependances2.remove(course)
                    return topological_sort()

        topological_sort()
        return sol if not any(g) else []

obj = Solution()
print(obj.findOrder(2, [[0,1],[1,0]]))
print(obj.findOrder(2, [[1,0]]))
print(obj.findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

O(|V|+|E|) time solution

The idea here is essentially the same, execept that now we are smarted about where to look. We begin with two hash tables. One to represent the graph, and a second one to represent the inverse of a graph. The reason for this will become clear later on. Next, we instantiate a queue. This queue is always going to contain courses that current have no prerequisites. We know that at the start, courses that have no prerequisites are those that have to dependances in our original graph g. Next we initiate a BFS. The front of the queue is always going to contain a course that has no prerequisites, so we can append it to our solution array. Next, we need to remove those dependances of the courses that is now completed. To do this, we iterate through the inverse graph of the course we removed (earlier we iterated through the entirety of the original graph). We also know that courses that will have their prerequisites removed, are the only options where there could potentially become no prerequisites. This is because we initially scanned the array for courses without prerequisites. So if a course becomes empty, add it into the q. An acylic graph will always reveal a topological ordering, but we can expect that our solution vector to contain the number of orderings as the original number of courses.

import queue
import collections

class Solution:
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        g = {i:set() for i in range(0, numCourses)}
        g_inv = collections.defaultdict(set)
        for i, j in prerequisites:
            g[i].add(j)
            g_inv[j].add(i)

        q = queue.Queue()
        for course in g:
            if not g[course]:
                q.put(course)

        topo_sort = []
        while not q.empty():
            front = q.get()
            topo_sort.append(front)

            for elm in g_inv[front]:
                g[elm].remove(front)
                if not g[elm]:
                    q.put(elm)

        return topo_sort if len(topo_sort) == numCourses else []


obj = Solution()
print(obj.findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
print(obj.findOrder(2, [[0, 1], [1, 0]]))
print(obj.findOrder(2, [[1, 0]]))