swift - 拓扑排序 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[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