# 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

'''

Last modified 3yr ago