Leetcode 207. Course Schedule — Topological Sort

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 <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Solution 1 — BFS with in-degree calculation

Solution 2 — DFS with cycle check

cycle detection using DFS is basically about understanding “back-tracing”. If you visit a node which you already visited, then, it means “cycle” exist.

When back trace, you cannot flag a node with “UNVISITED” back. This is graph, not a binary tree. If you only flag a node only “UNVISITED” or “VISITED”, you cannot filter out already visited node properly. You need another flag of “BACKTRACED”

When recursively DFSing, avoid visiting already BACKTRACED node because it will calculate things again. Here, if we don’t use BACKTRACED flag, but if we use “UNVISITED” flag for the backtraced nodes, you will visit all nodes over and over again.

Helpful youtube video