Golang solution (32ms) - Using DFS


  • 0
    func findOrder(numCourses int, prereqs [][]int) []int {
        graph := buildGraph(numCourses, prereqs)
        visited := make([]state, numCourses)
        result, index := make([]int, numCourses), numCourses - 1
        for course := range graph {
            if !findOrderHelper(course, graph, visited, result, &index) { return nil }
        }
        return result
    }
    
    func findOrderHelper(course int, graph [][]int, visited []state, result []int, index *int) bool {
        if visited[course] == partial {
            return false
        } else if visited[course] == complete {
            return true
        }
        visited[course] = partial
        for _, dependentCourse := range graph[course] {
            if !findOrderHelper(dependentCourse, graph, visited, result, index) { return false }
        }
        result[*index] = course
        *index--
        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.