14. Course Schedule

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    for _, pre := range prerequisites {
        graph[pre[1]] = append(graph[pre[1]], pre[0])
    }

    // 0=unvisited, 1=visiting, 2=visited
    state := make([]int, numCourses)

    for i := 0; i < numCourses; i++ {
        if state[i] == 0 {
            if hasCycle(graph, state, i) {
                return false
            }
        }
    }
    return true
}

func hasCycle(graph [][]int, state []int, node int) bool {
    state[node] = 1  // visiting

    for _, neighbor := range graph[node] {
        if state[neighbor] == 1 { return true }   // cycle
        if state[neighbor] == 0 {
            if hasCycle(graph, state, neighbor) { return true }
        }
    }

    state[node] = 2  // visited
    return false
}