Golang solution (23ms) - Using DFS


  • 0
    func canFinish(numCourses int, prereqs [][]int) bool {
        graph := buildGraph(numCourses, prereqs)
        visited := make([]state, numCourses)
        for course := range graph {
            if !canFinishHelper(course, graph, visited) { return false }
        }
        return true
    }
    
    func canFinishHelper(course int, graph [][]int, visited []state) bool {
        if visited[course] == partial {
            return false
        } else if visited[course] == complete {
            return true
        }
        visited[course] = partial
        for _, dependentCourse := range graph[course] {
            if !canFinishHelper(dependentCourse, graph, visited) { return false }
        }
        visited[course] = complete
        return true
    }
    
    type state int
    const (
        initial state = iota
        partial
        complete
    )
    
    func buildGraph(numCourses int, prereqs [][]int) [][]int {
        graph := make([][]int, numCourses)
        for i := 0; i < len(prereqs); i++ {
            graph[prereqs[i][1]] = append(graph[prereqs[i][1]], prereqs[i][0])
        }
        return graph
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.