-
Notifications
You must be signed in to change notification settings - Fork 0
/
coursesechdule.py
37 lines (32 loc) · 1.09 KB
/
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
33
34
35
36
37
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: 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