207 course schedule
207. Course Schedule
题目: https://leetcode.com/problems/course-schedule/
难度: Medium
思路：
就是考topological sort，用来判断directed graph是否有cycle
DFS 和 BFS都可以用来拓扑排序。
最简单的想法是每次取出indegree是0的node，然后把它和与之相关的edge都删了。一开始觉得这样的时间复杂度会很高，然后看到了这样写，参照：
http://bookshadow.com/weblog/2015/05/07/leetcode-course-schedule/
很聪明的写法
这里做了转成set以及添加removeList这样的操作是因为边list边做iterator这样的操作很危险
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
因为CLRS里面明确提到涂色法来处理DFS
搞了半天，写了一个涂色法，在超时的边缘。之所以超时边缘是因为每次都要去prerequisites里看，没有删减，不高效.
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
