## Course Schedule using Topological Sort

Topological Sort is an algorithm derived from Depth-First-Search(DFS). Topological Sort resolves the dependency network and works in acyclic directed graphs. It is also used in detecting cycles in directed graphs. In problems like loading packages, one needs to resolve dependent packages and load them first. Topological Sort helps in resolving dependent packages. Similar problems can be also solved like traversing and creating hierarchy, finding order, etc.

## Template for Topological Sort | 0 | heading |

- Before understanding Topological Sort, make sure you understand DFS.
- In the given example below, we load package ‘a’ in the system. We see ‘a’ has dependency packages ‘b’ , ‘c’ and ‘d’. ‘c’ is dependent on ‘d’.
- So we need to load packages in order as ‘d’, ‘c’, ‘b’ and then ‘a’.
- Here we will use recursive DFS and stack.
- We run DFS on every node
- If the node has no dependency or if the dependent of nodes are already in stack then we add that node to stack
- Below is the python code.
| 1 | list |

2 | image | |

```
import collections
def TopologicalSort(nodes):
edges = collections.defaultdict(set)
for u, v in nodes:
edges[u].add(v)
def dfs(vertex, visited, stack):
visited.add(vertex) #mark node visited
for u in edges.get(vertex, {}):
#check unvisited connected nodes
if u not in visited:
dfs(u, visited, stack)
#if all connected node visited, add the current node to stack
stack.append(vertex)
stack = [] #to store resolved nodes
visited = set()
for vertex in edges.keys():
if vertex not in visited:
dfs(vertex, visited, stack)
return stack #['d', 'c', 'b', 'a']
``` | 3 | code |

## Course Schedule(Cycle Detection) | 4 | heading |

207. Course Schedule | 5 | link |

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 | 6 | paragraph |

7 | image | |

## Intuition | 8 | subheading |

- This problem asks to check if there is any cycle in the graph.
- We don't need a stack here because we don’t need to return results. Instead, we return False if there is a cycle.
- Here we need to check three conditions - 1. If node visited, 2. If node partially visited 3. Node visited
- Instead of using a HashSet, we will use a hashmap to store node status in the visited hashmap.
- In DFS, if we found any node partially visited, which means we found a cycle.
- If the node is marked as visited, we return True because we have met the dependency.
- If the node is uninvited we call DFS.
| 9 | list |

```
def canFinish(numCourses, prerequisites):
#if no dependecy True
if not prerequisites:
return True
def dfs(vertex,visited):
#vertex dependecy met.
if visited[vertex] == 2:
return True
#case 2: visiting
visited[vertex] = 1
for v in edges.get(vertex, {}):
#case 3: visited
if (visited[v] == 2):
continue
elif (visited[v] == 1):
return False
else:
#case 1: unvisited node
if not dfs(v,visited):
return False
#we resolved dependecy
visited[vertex] = 2
return True
edges = collections.defaultdict(set)
for u, v in prerequisites:
edges[u].add(v)
visited = {v:0 for v in range(numCourses)}
for v in range(numCourses):
if not dfs(v,visited):
return False
return True
``` | 10 | code |

## Course Schedule II (Find Order) | 11 | heading |

210. Course Schedule II | 12 | link |

IThere 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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array. | 13 | paragraph |

```
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
``` | 14 | code |

15 | image | |

## Intuition | 16 | subheading |

- Here we use the same solution from the above problem but since we need a return order. We use a stack.
- We use a stack similar to the template above
| 17 | list |

```
def findOrder(numCourses, prerequisites):
#if no dependecy all course in any order
if not prerequisites:
return [u for u in range(numCourses)]
def dfs(vertex,visited,stack):
#vertex dependecy met.
if visited[vertex] == 2:
return True
#case 2: visiting
visited[vertex] = 1
for v in edges.get(vertex, {}):
#case 3: visited
if (visited[v] == 2):
continue
elif (visited[v] == 1):
return False
else:
#case 1: unvisited node
if not dfs(v,visited,stack):
return False
#we resolved dependecy
visited[vertex] = 2
stack.append(vertex)
return True
edges = collections.defaultdict(set)
for u, v in prerequisites:
edges[u].add(v)
stack = []
visited = {v:0 for v in range(numCourses)}
for v in range(numCourses):
if not dfs(v,visited,stack):
return []
return stack
``` | 18 | code |