Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  1. func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
  2. guard (prerequisites.count > 0) else {return true}
  3. var graph : [[Int]] = Array(repeating: [], count: numCourses + 1 )
  4. var inDegree : [Int] = Array(repeating: 0, count: numCourses + 1 )
  5. for x in prerequisites {
  6. graph[x[0]] += [x[1]]
  7. inDegree[x[0]] += 1
  8. }
  9.  
  10. for course in graph.enumerated() {
  11. print ("To finish course \(course.offset) you must have finished \(course.element)")
  12. }
  13.  
  14. for course in (inDegree.enumerated()) {
  15. print ("Course \(course.offset) needs \(course.element) courses to be complete")
  16. }
  17.  
  18. var outputArr = [Int]()
  19.  
  20. while let currentVertexIndx = (inDegree.enumerated().first { $0.element == 0 }?.offset) {
  21. outputArr.append( currentVertexIndx )
  22. for course in graph.enumerated() {
  23. if (course.element.contains(currentVertexIndx)) {
  24. inDegree[ course.offset ] -= 1
  25. }
  26. }
  27. inDegree[currentVertexIndx] = -1
  28. }
  29. return outputArr.count - 1 == numCourses
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement