# Course Schedule Topological Sort

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

```
#voodoo bfs solution
def canFinish(self, n, prerequisites):
G = [[] for i in range(n)]
degree = [0] * n
for j, i in prerequisites:
G[i].append(j)
degree[j] += 1
bfs = [i for i in range(n) if degree[i] == 0]
for i in bfs:
for j in G[i]:
degree[j] -= 1
if degree[j] == 0:
bfs.append(j)
return len(bfs) == n
```

```
#bfs solution
class Solution:
def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(n)]
indegree = [0] * n
ans = []
for pair in prerequisites:
course = pair[0]
prerequisite = pair[1]
adj[prerequisite].append(course)
indegree[course] += 1
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
while queue:
current = queue.popleft()
ans.append(current)
for next_course in adj[current]:
indegree[next_course] -= 1
if indegree[next_course] == 0:
queue.append(next_course)
return len(ans) == n
```

Topological Sort DFS Solution

```
class Solution:
def canFinish(self, numCourses, prerequisites):
self.adj_dict = defaultdict(set)
for i, j in prerequisites:
self.adj_dict[i].add(j)
self.Visited = [0] * numCourses
self.FoundCycle = 0
for i in range(numCourses):
if self.FoundCycle == 1: break # early stop if the loop is found
if self.Visited[i] == 0:
self.DFS(i)
return self.FoundCycle == 0
def DFS(self, start):
if self.FoundCycle == 1: return # early stop if the loop is found
if self.Visited[start] == 1:
self.FoundCycle = 1 # loop is found
if self.Visited[start] == 0: # node is not visited yet, visit it
self.Visited[start] = 1 # color current node as gray
for neib in self.adj_dict[start]: # visit all its neibours
self.DFS(neib)
self.Visited[start] = 2 # color current node as black
```

## Related Problems

A **transformation sequence** from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return *all the ***shortest transformation sequences*** from* beginWord *to* endWord*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words *[beginWord, s1, s2, ..., sk].

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Given an array nums of n integers where nums[i] is in the range [1, n], return *an array of all the integers in the range* [1, n] *that do not appear in* nums.

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.