Posted on 2023-07-13 16:25
Uriel 閱讀(64)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
圖論 、
閑來無事重切Leet Code
一共
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