Course Schedule

1. Problem Description

You have to take numCourses courses this semester, numbered from 0 to numCourses - 1.

Before taking some courses, you need to take prerequisite courses. The prerequisites are given as an array prerequisites, where prerequisites[i] = [ai, bi] means that if you want to study course ai, you must first study course bi.

For example, the prerequisite pair [0, 1] means that if you want to study course 0, you need to complete course 1 first. Determine whether it is possible to finish all courses. Return true if it is possible; otherwise return false.

2. Approach

• DFS
• BFS - topological sort

3. Implementation

3.1. DFS

package main

func canFinish(numCourses int, prerequisites [][]int) bool {
	graph := make([][]int, numCourses)
	for i := 0; i < len(graph); i++ {
		graph[i] = make([]int, 0)
	}

	for _, p := range prerequisites {
		graph[p[1]] = append(graph[p[1]], p[0])
	}

	flags := make([]int, numCourses)
	for i := 0; i < numCourses; i++ {
		if !canFinishDFS(graph, flags, i) {
			return false
		}
	}

	return true
}

func canFinishDFS(graph [][]int, flags []int, i int) bool {
	if flags[i] == 1 {
		return false
	}
	if flags[i] == -1 {
		return true
	}
	flags[i] = 1
	for _, j := range graph[i] {
		if !canFinishDFS(graph, flags, j) {
			return false
		}
	}

	flags[i] = -1
	return true
}

3.2. BFS - Topological Sort

// Topological sort
func canFinish2(numCourses int, prerequisites [][]int) bool {
	// Use an adjacency list to represent dependencies between nodes
	graph := make([][]int, numCourses)
	for i := 0; i < len(graph); i++ {
		graph[i] = make([]int, 0)
	}
	// Indegree table
	indegrees := make([]int, numCourses)

	// Initialize the adjacency list and indegree table
	for _, p := range prerequisites {
		// p[0] depends on p[1], meaning p[1] must be completed before p[0]
		// Therefore record p[1]->p[0]
		graph[p[1]] = append(graph[p[1]], p[0])
		indegrees[p[0]]++
	}

	// Kahn is essentially BFS, so use a queue
	// The queue stores nodes whose indegree is 0
	queue := make([]int, 0)
	for i := 0; i < numCourses; i++ {
		if indegrees[i] == 0 {
			queue = append(queue, i)
		}
	}

	//res := make([]int, 0)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		//res = append(res, node)

		numCourses--
		for _, out := range graph[node] {
			indegrees[out]--
			if indegrees[out] == 0 {
				queue = append(queue, out)
			}
		}
	}
	//return len(res) == numCourses
	return numCourses == 0
}

4. References

• 207. Course Schedule - LeetCode