# Topological Sorting | LeetCode Course Schedule I/II | Graph, DFS, BFS

# What’s Topological Sorting

*Clearer Article Read **Topological Sorting | LeetCode Course Schedule I/II | Graph, DFS, BFS — Hung, Chien-Hsiang 洪健翔 | Blog (chienhsiang-hung.github.io)*

Topological sorting for **Directed Acyclic Graph (DAG)** is a linear ordering of vertices such that for every directed edge u v, **vertex u comes before v** in the ordering.1

**Note:** Topological Sorting for a graph is not possible if the graph is not a DAG. (i.e. If there is a loop/cycle in the Graph)

*Below is the implementation of the above approach:*

# Examples

# Course Schedule II

**LeetCode 210. Course Schedule II**2

It’s basically a slightly advanced version of Course Schedule in which *you need to record the courses this time*.

At the first I tried to approach this by **DFS**.

from collections import defaultdict# DAG - topological sorting

class Solution:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

if not prerequisites:

return list( range(numCourses) ) adj_lit = defaultdict(list)

for c0, c1 in prerequisites:

adj_lit[c0].append(c1) def traverse(c0):

'''check a vertix's prerequisite'''

visited[c0] = True

for cs in adj_lit[c0]:

if not visited[cs]:

traverse(cs)# DFS

stack.append(c0) visited = [False] * numCourses

stack = []

adj_keys = list(adj_lit.keys())# to handle defaultdict's size changed during iteration in line-12

for c0 in adj_keys:

if not visited[c0]:

traverse(c0)

return stack# Failed at task like:# n = 2# prerequisites = [[0,1],[1,0]]

But I quickly realized I’ve *missed to handle the loop*. Then I tried again.

###### still failed at n=2, pre=[[0,1],[1,0]] ######

class Solution:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

adj_list = [[] for _ in range(numCourses)]

for c0, c1 in prerequisites:

adj_list[c0].append(c1) def DFS(c0, master):

visited[c0] = True

for c1 in adj_list[c0]:

# detect loop (cycle)

if adj_list[c1] == master:

acycle[0] = False if not visited[c1]:

DFS(c1, master)

output.append(c0)

visited = [False] * numCourses

output = []

acycle = [True]

for c0 in range(numCourses):

if acycle[0] == False:

return []

if not visited[c0]:

# independent course

if adj_list[c0] == []:

visited[c0] = True

output.append(c0) else:

DFS(c0, c0)

return output###### still failed at n=2, pre=[[0,1],[1,0]] ######

Still missing…

Then I adopted the solution from archit91 with **BFS** approach. It’s nicely structured and well-run.

from collections import defaultdict, dequeclass Solution:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

graph = defaultdict(list)

in_degree = [0] * numCourses

for next_c, pre_c in prerequisites:

graph[pre_c].append(next_c)

in_degree[next_c] += 1

BFS_q = deque()

for cs in range(numCourses):

if in_degree[cs] == 0:

BFS_q.append(cs)

ans = []

while BFS_q:

curr = BFS_q.popleft()

ans.append(curr)

for next_c in graph[curr]:

in_degree[next_c] -= 1

if in_degree[next_c] == 0:

BFS_q.append(next_c)

return ans if len(ans)==numCourses else []

# Course Schedule

**LeetCode 207. Course Schedule**3 *[Medium]*

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`

.

**Example 1:**

Input:numCourses = 2, prerequisites = [[1,0]]

Output:true

Explanation:There are a total of 2 courses to take.

To take course 1 you should have finished course 0. So it is possible.

**Example 2:**

Input:numCourses = 2, prerequisites = [[1,0],[0,1]]

Output:false

Explanation:There are a total of 2 courses to take.

To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

**Constraints:**

`1 <= numCourses <= 2000`

`0 <= prerequisites.length <= 5000`

`prerequisites[i].length == 2`

`0 <= ai, bi < numCourses`

- All the pairs prerequisites[i] are
**unique**.

**Thinking**

This is basically the simpler version of Course Schedule II.

# if there is a loop, it won't be possible to finish all coursesfrom collections import defaultdict, dequeclass Solution:

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

graph = defaultdict(list)

pre_cs_list = [0] * numCourses for next_c, pre_c in prerequisites:

graph[pre_c].append(next_c)

pre_cs_list[next_c] += 1

q = deque()

# check independent cources

for i in range(numCourses):

if pre_cs_list[i] == 0:

q.append(i)

ans = []

while q:

curr = q.popleft()

ans.append(curr) for next_c in graph[curr]: pre_cs_list[next_c] -= 1

if pre_cs_list[next_c] == 0:

q.append(next_c)

return len(ans) == numCourses