Course Schedule

LeetCode 207 · View on LeetCode

Determine if all courses can be finished given prerequisite pairs. Uses Kahn's algorithm (BFS topological sort).

How it works: inDegree[i] counts how many unfinished prerequisites course i still has. We start by enqueueing courses with zero prerequisites (they're ready to take). When we "complete" a course, we decrement inDegree for each of its dependents — inDegree[nei]-- means "you needed me, and I'm done now." When a course's in-degree hits 0, all its prerequisites are satisfied, so it becomes takeable (enqueue it). If a cycle exists, some courses never reach 0 and count < numCourses.

package main

import "fmt"

func canFinish(numCourses int, prerequisites [][]int) bool {
	adj := make([][]int, numCourses)
	inDegree := make([]int, numCourses)
	for _, p := range prerequisites {
		crs, pre := p[0], p[1]
		adj[pre] = append(adj[pre], crs)
		inDegree[crs]++
	}

	queue := []int{}
	for i := 0; i < numCourses; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	count := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		count++
		for _, nei := range adj[node] {
			inDegree[nei]--
			if inDegree[nei] == 0 {
				queue = append(queue, nei)
			}
		}
	}

	return count == numCourses
}

func main() {
	fmt.Println(canFinish(4, [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}})) // true
	fmt.Println(canFinish(2, [][]int{{1, 0}, {0, 1}}))                  // false
}