# Course Schedule
An example of [[cycle-detection]] in graph.
## Approach 1: [[topological-sort|Topological Sort]] with [[kahn|Kahn's Algorithm]]
```python
indegs = [0] * numCourses
adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
indegs[course] += 1
adj[prereq].append(course)
queue = deque([
course for course, indeg in enumerate(indegs) if not indeg
])
taken = 0
while queue:
prereq = queue.popleft() # no prereq required, take this!
taken += 1
for course in adj[prereq]:
indegs[course] -= 1 # one more prereq satisfied
if not indegs[course]:
# all prereqs satisfied
queue.append(course)
return taken == numCourses
```
## Approach 2: [[dfs|DFS]]
```python
adj = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
adj[prereq].append(course)
visited = [False] * numCourses
in_stack = [False] * numCourses
def dfs(v):
nonlocal visited, in_stack, adj
if in_stack[v]:
return True
if visited[v]:
return False
visited[v] = True
in_stack[v] = True
if any(dfs(neighbor) )
for neighbor in adj[v]:
if dfs(neighbor):
return True
in_stack[v] = False
return False
return not any(dfs(v) for v in range(numCourses))
```