207 course schedule

207. Course Schedule

DFS 和 BFS都可以用来拓扑排序。

class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
degrees = [ 0 for i in range(numCourses)]
childs = [[] for i in range(numCourses)]
for front, tail in prerequisites:
degrees[front] += 1
childs[tail].append(front)

courses = set(range(numCourses))
flag = True

while flag and len(courses):
flag = False
removeList = []
for x in courses:
if degrees[x] == 0:
for child in childs[x]:
degrees[child] -= 1
removeList.append(x)
flag = True
for x in removeList:
courses.remove(x)
return len(courses) == 0



class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
def dfs(i, colors, prerequisites):
colors[i] = 'G'
#print i, colors
for front, tail in prerequisites:
if tail == i:
if colors[front] == 'G':
return False
elif colors[front] == 'B':
continue
elif dfs(front, colors, prerequisites) == False:
return False
colors[i] = 'B'
return True

colors = ['W' for i in range(numCourses)]
for i in range(numCourses):
if colors[i] == 'W':
if dfs(i, colors, prerequisites) == False:
return False
return True