course-schedule-bfs.go

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

func canFinish(numCourses int, prerequisites [][]int) bool {
    if len(prerequisites) == 0 {
        return true
    }
    
    graph := make([][]int, numCourses)
    inDegree := make([]int, numCourses)
    
    for _, pair := range prerequisites {
        from, to := pair[0], pair[1]
        graph[from] = append(graph[from], to)
        inDegree[to]++
    }
    
    queue := make([]int, 0, numCourses)
    
    for v, count := range inDegree {
        if count == 0 {
            queue = append(queue, v)
        }
    }
    
    visited := 0
    
    for len(queue) > 0 {
        top := queue[0]
        queue = queue[1:]

        for _, child := range graph[top] {
            inDegree[child]--
            
            if inDegree[child] == 0 {
                queue = append(queue, child)
            }
        }
        
        visited++
    }
    
    return visited == numCourses
}