-
Notifications
You must be signed in to change notification settings - Fork 0
/
coursesechdule.py
32 lines (27 loc) · 1022 Bytes
/
coursesechdule.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if not prerequisites:
return True
def DFS(node):
# Cycle detected.
if visited[node] == 1:
return False
# Visit this node, explore neighbors.
visited[node] = 1
for nbr in G[node]:
if visited[nbr] != 2 and not DFS(nbr):
return False
# Done visiting node.
visited[node] = 2
return True
# Build the graph.
G = collections.defaultdict(list)
for postreq, course in prerequisites:
G[course].append(postreq)
G[postreq] # Make sure nodes are made for courses with no postreqs.
visited = [0] * numCourses
for node in G:
if not visited[node]:
if not DFS(node):
return False
return True