course-schedule.go

// https://leetcode.com/problems/course-schedule

const (
    free = byte(0)
    observed = byte(1)
    visited = byte(2)
)

func canFinish(numCourses int, prerequisites [][]int) bool {
    if len(prerequisites) == 0 {
        return true
    }
    
    graph := make([][]int, numCourses)
    states := make([]byte, numCourses)
    
    for _, pair := range prerequisites {
        from, to := pair[0], pair[1]
        graph[from] = append(graph[from], to)
    }
    
    result := true
    
    for i := 0; i < numCourses && result; i++ {
        if isCycle(graph, i, states) {
            result = false
        }
    }
    
    return result
}

func isCycle(graph [][]int, from int, states []byte) bool {
    if len(graph[from]) == 0 || states[from] == visited {
        return false
    }
    
    if states[from] == observed {
        return true
    }
    
    states[from] = observed
    
    for _, to := range graph[from] {
        if from == to || isCycle(graph, to, states) {
            return true
        }
    }
    
    states[from] = visited
    
    return false
}