func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var inDegrees = Array(repeating: 0, count: numCourses)
var dict = [Int: [Int]]()
for prerequisite in prerequisites {
inDegrees[prerequisite[0]] += 1
if let list = dict[prerequisite[1]] {
dict[prerequisite[1]] = list + [prerequisite[0]]
} else {
dict[prerequisite[1]] = [prerequisite[0]]
}
}
var queue = [Int]()
var answer = [Int]()
for (index, inDegree) in inDegrees.enumerated() {
if inDegree == 0 {
queue.append(index)
}
}
while !queue.isEmpty {
let currentCourse = queue.removeFirst()
answer.append(currentCourse)
if let list = dict[currentCourse] {
for course in list {
inDegrees[course] -= 1
if inDegrees[course] == 0 {
queue.append(course)
}
}
}
}
return answer.count == numCourses ? answer : []
}
More than 5 years have passed since last update.
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme