题目
思路
拓扑排序，BFS，记录下来遍历的顺序即可。
代码
class Solution:
"""
@param: numCourses: a total of n courses
@param: prerequisites: a list of prerequisite pairs
@return: the course order
"""
def getCourseDict(self, prerequisites):
course_dict = {}
for course
in prerequisites:
if course[
1]
in course_dict:
course_dict[course[
1]].append(course[
0])
else:
course_dict[course[
1]] =[]
course_dict[course[
1]].append(course[
0])
return course_dict
def getPreCourseNum(self, prerequisites):
pre_course_num_dict = {}
for course
in prerequisites:
if course[
0]
in pre_course_num_dict:
pre_course_num_dict[course[
0]] +=
1
else:
pre_course_num_dict[course[
0]] =
1
return pre_course_num_dict
def getStartCourse(self, pre_course_num_dict, n):
start_course_list = []
for i
in range(n):
if i
not in pre_course_num_dict:
start_course_list.append(i)
return start_course_list
def bfs(self, course_dict, pre_course_num_dict, start_course_list):
res_list = []
queue = []
for course
in start_course_list:
queue.append(course)
while queue:
course = queue[
0]
queue.pop(
0)
res_list.append(course)
if course
in course_dict:
for next_course
in course_dict[course]:
pre_course_num_dict[next_course] -=
1
if pre_course_num_dict[next_course] ==
0:
queue.append(next_course)
for val
in pre_course_num_dict.values():
if val:
return []
return res_list
def findOrder(self, numCourses, prerequisites):
if not numCourses:
return []
course_dict = self.getCourseDict(prerequisites)
pre_course_num_dict = self.getPreCourseNum(prerequisites)
start_course_list = self.getStartCourse(pre_course_num_dict, numCourses)
if not start_course_list:
return []
return self.bfs(course_dict, pre_course_num_dict, start_course_list)
