Топологическая сортировка Swift

Question

Я пытаюсь реализовать топологическую сортировку в Swift, используя следующую теорию.

https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf

Мой код:

func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    guard (prerequisites.count > 0) else {return true}
    var graph : [[Int]] = Array(repeating: [], count: numCourses + 1)
    var inDegree : [Int] = Array(repeating: 0, count: numCourses + 1 )
    for x in prerequisites {
        graph[x[0]] = [x[1]]
        inDegree[x[0]] += 1
    }
    for course in graph.enumerated() {
        print ("To finish course \(course.offset) you must have finished \(course.element)")
    }

    for course in (inDegree.enumerated()) {
        print ("Course \(course.offset) needs \(course.element) courses to be complete")
    }

    var outputArr = [Int]()

    while let currentVertexIndx = (inDegree.enumerated().first { $0.element == 0 }?.offset) {
        outputArr.append( currentVertexIndx )
        for course in graph.enumerated() {

            if (course.element.contains(currentVertexIndx)) {
                inDegree[ course.offset ] -= 1
            }
        }

        inDegree[currentVertexIndx] = -1
    }
    return outputArr.count >= numCourses
}

Тесты с правильнымиответы:

//canFinish(1, [[1,0]]) // true - to take course 1 you should have finished course 0
//canFinish(2, [[1,0],[0,1]]) // false - to take course 1 you have to have finished course 0, to take 0 you have to have finished course 1
//canFinish(1, []) // true
//canFinish(3, [[1,0],[2,0]]) // true
//canFinish(3, [[2,0],[2,1]]) // true

Тест с неправильным ответом

canFinish(10, [[5,6],[0,2],[1,7],[5,9],[1,8],[3,4],[0,6],[0,7],[0,3],[8,9]]) // true, but returns false

Вопрос: Мой код не работает для ввода выше, используя теорию, связанную с Washington.edu.Что не так?

Answer 1

Вы должны правильно заполнить graph:

graph[x[0]] += [x[1]]

Что даст правильный результат в данном примере:

canFinish(10, [[5,6],[0,2],[1,7],[5,9],[1,8],[3,4],[0,6],[0,7],[0,3],[8,9]]) //true