Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一共
numCourses门课,
prerequisites中的每个pair [a, b]表示a的先修课是b,问是否有可能修完所有课
BFS+拓扑排序思想


 1 #207
 2 #Runtime: 74 ms (Beats 75.97%)
 3 #Memory: 14.5 MB (Beats 97.82%)
 4 
 5 class Solution(object):
 6     def canFinish(self, numCourses, prerequisites):
 7         """
 8         :type numCourses: int
 9         :type prerequisites: List[List[int]]
10         :rtype: bool
11         """
12         ind = [0] * numCourses
13         adj = [[] for _ in range(numCourses)]
14         for i in range(len(prerequisites)):
15             a, b = prerequisites[i]
16             adj[b].append(a)
17             ind[a] += 1
18         q = deque()
19         for i in range(numCourses):
20             if not ind[i]:
21                 q.append(i)
22         ans = []
23         while q:
24             node = q.popleft()
25             ans.append(node)
26             for i in adj[node]:
27                 ind[i] -= 1
28                 if ind[i] == 0:
29                     q.append(i)
30         return len(ans) == numCourses

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理