leetcode 207

course_schedule.kt

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        val graph = Array(numCourses) { BooleanArray(numCourses) {false} }
        val requirement = IntArray(numCourses) {0}
        
        var course: Int
        var preCourse: Int
        for(i in prerequisites.indices) {
            course = prerequisites[i][0]
            preCourse = prerequisites[i][1]
            
            graph[preCourse][course] = true
            ++requirement[course]
        }
        
        //>> find course without requirement
        val queue = mutableListOf<Int>()
        for(i in requirement.indices) {
            if(requirement[i] == 0) {
                queue.add(i)
            }
        }
        
        var cnt = 0
        while(queue.isNotEmpty()) {
            ++cnt
            course = queue.removeAt(0)
            
            for(i in 0 until numCourses) {
                if(graph[course][i]) {
                    graph[course][i] = false
                    
                    --requirement[i]
                    if(requirement[i] == 0) {
                        queue.add(i)
                    }
                }
            }
        }
        
        return cnt == numCourses
    }
}