1def findOrder(numCourses, prerequisites):
2 graph = [[] for _ in range(numCourses)]
3 for course, prereq in prerequisites:
4 graph[prereq].append(course)
5
6 result = []
7 visited = [False] * numCourses
8 visiting = [False] * numCourses
9
10 def dfs(current):
11 if visited[current]:
12 return True
13
14 # Cycle detected
15 if visiting[current]:
16 return False
17
18 visiting[current] = True
19 neighbors = graph[current]
20 for neighbor in neighbors:
21 if not dfs(neighbor):
22 return False
23
24 visited[current] = True
25 visiting[current] = False
26 result.append(current)
27 return True
28
29 for i in range(numCourses):
30 if not visited[i]:
31 if not dfs(i):
32 return []
33
34 result.reverse()
35 return result| Variable | Value |
|---|---|
numCourses | 4 |
prerequisites | Matrix(4x2) [[1,0]...] |
graph | - |
course | - |
prereq | - |
result | - |
visited | - |
visiting | - |
i | - |
| Depth | Function Call |
|---|---|
| 1 | findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) |
1def findOrder(numCourses, prerequisites):
2 graph = [[] for _ in range(numCourses)]
3 for course, prereq in prerequisites:
4 graph[prereq].append(course)
5
6 result = []
7 visited = [False] * numCourses
8 visiting = [False] * numCourses
9
10 def dfs(current):
11 if visited[current]:
12 return True
13
14 # Cycle detected
15 if visiting[current]:
16 return False
17
18 visiting[current] = True
19 neighbors = graph[current]
20 for neighbor in neighbors:
21 if not dfs(neighbor):
22 return False
23
24 visited[current] = True
25 visiting[current] = False
26 result.append(current)
27 return True
28
29 for i in range(numCourses):
30 if not visited[i]:
31 if not dfs(i):
32 return []
33
34 result.reverse()
35 return result