207 Course Schedule

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, is it possible for you to finish all courses?

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 it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

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.

The Idea: Implement topological sort. First construct an adjacency set graph. Iterate through the graph to find a independent node. This node represents one possible course to take. Decrement numCourses as independent courses are selected. Once a course is selected, removed this course from the graph, and all other dependancies it has. Repeat this process until numCourses is 0 (all fullfilled), or a cycle is found (this is identified when no independent courses are found). Finally, return True if the graph is empty (all courses are fullfilled), and False otherwise.

Complexity: O(n^3) time, and O(n) space

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        if not prerequisites or not prerequisites[0]:
            return True

        g = {}
        for pair in prerequisites:
            if not g.__contains__(pair[0]):
                g[pair[0]] = set()
            if not g.__contains__(pair[1]):
                g[pair[1]] = set()

        for pair in prerequisites:
            g[pair[0]].add(pair[1])

        stop = False
        while not stop:
            stop = True
            if numCourses is 0:
                return True

            for key, _set in g.items():
                if not _set:
                    stop = False
                    numCourses -= 1
                    del g[key]
                    for _, _set2 in g.items():
                        if key in _set2:
                            _set2.remove(key)
                    break

        if not g:
            return True
        else:
            return False

O(N) time solution

The first thing to recognize is that if a graph is acyclic, then it must have a topological ordering. In the same way, if the graph has a topological ordering, then it is acyclic. So we can boil this problem down to answering the question whether or not the graph contains any cycles. If there are cycles, then the courses can not be completed. Otherwise this must exist a topological ordering, and the so the courses can be finished.

A cycle exists in a graph if at any time during we reach a node that is already within our recusion stack. When this is the case, we know that their exists a path from where we started (bottom of stack) to somewhere we've already been (somewhere in recursion stack). To avoid repeating the same recursions we maintain a visited set that always collects unvisited nodes we come across.

class Solution:
    def get_directed_graph(self, prereqs):
        g = {}
        for pair in prereqs:
            g[pair[0]] = set()
            g[pair[1]] = set()

        for pair in prereqs:
            g[pair[0]].add(pair[1])

        return g

    def cyclic(self, g):
        path = set()
        visited = set()

        def DFS(vertex):
            if vertex in visited:
                return False

            visited.add(vertex)
            path.add(vertex)

            for neighbour in g[vertex]:
                if neighbour in path or DFS(neighbour):
                    return True
            path.remove(vertex)

            return False

        return any(DFS(v) for v in g)

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        # no prereqs -> [[]]
        if not prerequisites or not prerequisites[0]:
            return True

        # create directed graph
        g = self.get_directed_graph(prerequisites)
        if self.cyclic(g):
            return False
        return True

Testing

obj = Solution()
print(obj.canFinish(3, [[0,1],[0,2],[1,2]])) # True
print(obj.canFinish(2, [[1,0]])) # True
print(obj.canFinish(2, [[1,0],[0,1]])) # False

'''
TEST 1
visited: {0}
path:    {0}
visited: {0, 1}
path:    {0, 1}
visited: {0, 1, 2}
path:    {0, 1, 2}
path:    {0, 1}
path:    {0}
path: set()
True

TEST 2
visited: {1}
path:    {1}
visited: {0, 1}
path:    {0, 1}
path:    {1}
path:    set()
True

TEST 3
visited: {1}
path:    {1}
visited: {0, 1}
path:    {0, 1}
False
'''