[Swift]LeetCode210. 课程表 II | Course Schedule II_app

概述There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:

There are a total of n courses you have to take,labeled from 0 to n-1.

Some courses may have prerequisites,for example to take course 0 you have to first take course 1,which is expressed as a pair: [0,1]

Given the total number of courses and a @R_404_6818@ of prerequisite pairs,return the ordering of courses you should take to finish all courses.

There may be multiple correct orders,you just need to return one of them. If it is impossible to finish all courses,return an empty array.

Example 1:

input: 2,[[1,0]] Output: Explanation: There are a total of 2 courses to take. To take course 1 you should have finished                course 0. So the correct course order is [0,1][0,1] .

Example 2:

input: 4,0],[2,[3,1],2]]Output: Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both                  courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.              So one correct course order is . Another correct ordering is [0,1,2,3] or [0,3][0,3] .

Note:

The input prerequisites is a graph represented by a @R_404_6818@ of edges,not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2,0]] 输出: 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4,2]]输出: 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。     因此，一个正确的课程顺序是  。另一个正确的排序是  。[0,3]

说明:

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。你可以假定输入的先决条件中没有重复的边。

提示:

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。

拓扑排序也可以通过 BFS 完成。

104ms

 1 class Edge { 2      3     let y: Int 4     var next: Edge? 5      6     init(_ y: Int) { 7         self.y = y 8     } 9 }10 11 struct Graph {12     13     var edges: [Edge?]14     var indegree: [Int]15     16     init(numOfVertices: Int) {17         self.edges = [Edge?](repeating: nil,count: numOfVertices)18         self.indegree = [Int](repeating: 0,count: numOfVertices)19     }20     21     mutating func insertEdge(_ x: Int,_ y: Int) {22         23         let newEdge = Edge(y)24         newEdge.next = edges[x]25         26         edges[x] = newEdge27         indegree[y] += 128     }29 }30 31 32 class Solution {33     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] {34         35         var graph = createGraph(numCourses: numCourses,prerequisites: prerequisites)        36         37         var queue: [Int] = []38         for x in 0..<graph.indegree.count {39             if graph.indegree[x] == 0 {40                 queue.append(x)41             }42         }43         44         var order: [Int] = []45         46         while !queue.isEmpty {47             48             var nextQueue: [Int] = []49             50             for x in queue {51                 order.append(x)52                 53                 var edge = graph.edges[x]54                 while let _edge = edge {55                     let y = _edge.y56                     graph.indegree[y] -= 157                     58                     if graph.indegree[y] == 0 {59                         nextQueue.append(y)60                     }61                     62                     edge = _edge.next63                 }64             }65             66             queue = nextQueue67         }68         69         return order.count == numCourses ? order : []70     }71     72     func createGraph(numCourses: Int,prerequisites: [[Int]]) -> Graph {73         74         var graph = Graph(numOfVertices: numCourses)75         76         for pair in prerequisites {77             let y = pair[0]78             let x = pair[1]79             80             graph.insertEdge(x,y)81         }82         83         return graph84     }85     86 }

108ms

 1 class Solution { 2     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] { 3  4         var graph = [[Int]](repeating:[Int](),count: numCourses) 5         var coursesIn = Array(repeating: 0,count: numCourses) 6         var res = [Int]() 7         for a in prerequisites { 8             graph[a[1]].append(a[0]) 9             coursesIn[a[0]] += 110         }11         var q = [Int]()12         for i in coursesIn.indices {13             if coursesIn[i] == 0 { q.append(i) }14         }15         while !q.isEmpty {16             var t = q.removeFirst()17             res.append(t)18             for a in graph[t] {19                 coursesIn[a] -= 120                             21                 if coursesIn[a] == 0 { q.append(a) }22 23             }24         }25         if res.count != numCourses { res.removeAll() }26         return res27     }28 }

108ms

 1 class Solution { 2     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] { 3         var res:[Int] = [Int]() 4         var graph:[[Int]] = [[Int]](repeating:[Int](),count:numCourses) 5         var ins:[Int] = [Int](repeating:0,count:numCourses) 6         for a in prerequisites 7         { 8             graph[a[1]].append(a[0]) 9             ins[a[0]] += 110         }11         var q:[Int] = [Int]()12         for i in 0..<numCourses13         {14             if ins[i] == 015             {16                 q.append(i)17             }18         }19         while(!q.isEmpty)20         {21             var t:Int = q.first!22             res.append(t)23             q.removeFirst()24             for num in graph[t]25             {26                 ins[num] -= 127                 if ins[num] == 028                 {29                     q.append(num)30                 }31             }32         }33         if res.count != numCourses34         {35             res.removeAll()36         }37         return res38     }39 }

112ms

 1 class Solution { 2     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] { 3         if numCourses == 0 { 4             return [] 5         } else if numCourses == 1 { 6             return [0] 7         } 8          9         var inDegree = Array(repeating: 0,count: numCourses)10         var graph = [Int: [Int]]()11         for prerequisite in prerequisites {12             inDegree[prerequisite[0]] += 113             graph[prerequisite[1],default: [Int]()].append(prerequisite[0])14         }15         var queue = [Int]()16         for course in 0 ..< numCourses where inDegree[course] == 0{17             queue.append(course)18         }19         var result = [Int]()20         while !queue.isEmpty {21             let course = queue.removeFirst()22             result.append(course)23             if let courses = graph[course] {24                 for course in courses {25                     inDegree[course] -= 126                     if inDegree[course] == 0 {27                         queue.append(course)28                     }29                 }30             }31         }32         return result.count == numCourses ? result : []33     }34 }

116ms

 1 class Course { 2     let number: Int 3     var dependents: [Int: Course] 4     var numberOfPrereq: Int 5  6     init(number: Int) { 7         self.number = number 8         dependents = [Int: Course]() 9         numberOfPrereq = 010     }11 }12 13 class Solution {14     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] {15         var courses = [Course]()16 17         for courseNumber in 0..<numCourses {18             courses.append(Course(number: courseNumber))19         }20 21         // Build the graph22         for prerequisite in prerequisites {23             let courseNum = prerequisite[0]24             let prerequisiteNum = prerequisite[1]25 26             let course = courses[courseNum]27             let pre    = courses[prerequisiteNum]28             course.numberOfPrereq += 129 30             // Add an edge31             pre.dependents[course.number] = course32         }33 34         var result = [Int]()35 36         var stack = [Course]()37         for courseNumber in 0..<numCourses {38             let course = courses[courseNumber]39             if course.numberOfPrereq == 0 {40                 stack.append(course)41             }42         }43 44         while !stack.isEmpty {45             let c = stack.removeLast()46 47             // Add to result48             result.append(c.number)49 50             for el in c.dependents {51                 // Remove edge52                 c.dependents.removeValue(forKey: el.value.number)53                 el.value.numberOfPrereq -= 154                 if el.value.numberOfPrereq == 0 {55                     stack.append(el.value)56                 }57             }58         }59 60         // Should have no edge left,otherwise we have a cycle61         for course in courses {62             if course.numberOfPrereq != 0 {63                 return []64             }65         }66 67         return result68     }69 }

120ms

 1 class Solution { 2     func findOrder(_ total: Int,_ courses: [[Int]]) -> [Int] { 3          var dict: [Int: [Int]] = [:] 4         var prev: [Int] = Array(repeating: 0,count: total) 5         for course in courses { 6             prev[course.first!] += 1 7             dict[course.last!,default: []].append(course.first!) 8         } 9         var count = 010         var queue: [Int] = []11         for (index,num) in prev.enumerated() {12             if num == 0 {13                 queue.append(index)14             }15         }16         var res: [Int] = []17         while !queue.isEmpty {18             let num = queue.first!19             queue.removeFirst()20             res.append(num)21             if let nextCourses = dict[num],!courses.isEmpty {22                 for course in nextCourses {23                     prev[course] -= 124                     if prev[course] == 0 {25                         queue.append(course)26                     }27                 }28             }29         }30         if res.count != total {31             return []32         }33         return res34     }35 }

128ms

 1 class Edge { 2      3     let y: Int 4     var next: Edge? 5      6     init(y: Int) { 7         self.y = y 8     } 9 }10 11 struct Graph {12     var edges: [Edge?]13     var edgeCount: [Int]14     var indegree: [Int]15     16     init(vertexCount: Int) {17         self.edges = [Edge?](repeating: nil,count: vertexCount)18         self.edgeCount = [Int](repeating: 0,count: vertexCount)19         self.indegree = [Int](repeating: 0,count: vertexCount)20     }21 }22 23 class Solution {24     25     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] {26         guard numCourses > 0 else {27             return []28         }29         guard numCourses > 1 else {30             return [0]31         }32         33         34         var graph = graphFrom(numCourses: numCourses,prerequisites: prerequisites)35         var courSEOrder: [Int] = []36         37         var queue: [Int] = []38         for x in 0..<graph.edges.count {39             if graph.indegree[x] == 0 {40                 queue.append(x)41             }42         }43         44         while !queue.isEmpty {45             46             var nextQueue: [Int] = []47             48             for x in queue {49                 courSEOrder.append(x)50                 51                 var edge = graph.edges[x]52                 while let _edge = edge {53                     let y = _edge.y54                     graph.indegree[y] -= 155                     56                     if graph.indegree[y] == 0 {57                         nextQueue.append(y)58                     }59                     60                     edge = _edge.next61                 }62             }63             64             queue = nextQueue65         }66         67         68         return courSEOrder.count == numCourses ? courSEOrder : []69     }70     71     72     73     func graphFrom(numCourses: Int,prerequisites: [[Int]]) -> Graph {74         var graph = Graph(vertexCount: numCourses)75         76         for pair in prerequisites {77             78             let x = pair[1]79             let y = pair[0]80             81             let newEdge = Edge(y: y)82             newEdge.next = graph.edges[x]83             84             graph.edges[x] = newEdge85             graph.edgeCount[x] += 186             graph.indegree[y] += 187         }88         89         return graph90     }91 }

132ms

 1 class Solution { 2 class Node: Hashable { 3     static func == (lhs: Node,rhs: Node) -> Bool { 4         return lhs.val == rhs.val 5     } 6      7     var val: Int 8     var indegree: Set<Node> 9     var outdegree: Set<Node>10     11     init(_ val: Int) {12         self.val = val13         self.indegree = Set<Node>()14         self.outdegree = Set<Node>()15     }16     17     public var hashValue: Int {18         return val19     }20 }21 22 23 func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] {24     guard numCourses > 0 else {25         return [Int]()26     }27     28     var map = [Int: Node]()29     var queue = [Node]()30     var set = Set<Node>()31     var res = [Int]()32     33     for num in 0..<numCourses {34         map[num] = Node(num)35     }36     37     for pair in prerequisites {38         map[pair[0]]?.indegree.insert(map[pair[1]]!)39         map[pair[1]]?.outdegree.insert(map[pair[0]]!)40     }41     42     for (_,node) in map {43         if node.indegree.count == 0 {44             queue.append(node)45             set.insert(node)46             res.append(node.val)47         }48     }49     50     while !queue.isEmpty {51         let curr = queue.removeFirst()52         for node in curr.outdegree {53             node.indegree.remove(curr)54             55             if node.indegree.count == 0,!set.contains(node) {56                 queue.append(node)57                 set.insert(node)58                 res.append(node.val)59             }60         }61     }62     63     return res.count == numCourses ? res : [Int]()64  }65 }

160ms

 1 class Solution { 2     func findOrder(_ n: Int,_ prerequisites: [[Int]]) -> [Int] { 3         var indegree = [Int](repeating: 0,count: n) 4         var adjMap = [Int: Set<Int>]() 5         for prerequisite in prerequisites { 6             let first = prerequisite[1] 7             let second = prerequisite[0] 8             indegree[second] += 1 9             var newSet : Set<Int>10             if let s = adjMap[first]{11                 newSet = s12             }else {13                 newSet = Set<Int>()14             }15             newSet.insert(second)16             adjMap[first] = newSet17         }18         var queue = [Int]()19         for i in 0 ..< n{20             if indegree[i] == 0{21                 queue.append(i)22             }23         }24         var res = [Int]()25         while !queue.isEmpty{26             let cur = queue.removeFirst()27             res.append(cur)28             if let map = adjMap[cur]{29                 for adj in map{30                     indegree[adj] -= 131                     if indegree[adj] == 0{32                         queue.append(adj)33                     }34                 }35             }36         }37         if res.count != n {38             return [Int]()39         }40         return res41     }42 }

184ms

 1 class Solution { 2   struct Node{ 3     var nodes: [Int] = [Int]() 4     var isSeen: Bool = false 5   } 6   var graph: [Node] = [Node]() 7   var order: [Int] = [Int]() 8   var graphHasCycle: Bool = false 9   var isInStack: [Bool] = [Bool]()10   func dfs(_ node: Int){11     isInStack[node] = true12     graph[node].isSeen = true13     for to in graph[node].nodes{14       if !graph[to].isSeen{15         dfs(to)16       }else{17         if isInStack[to] {18           graphHasCycle = true19         }20       }21     }22     isInStack[node] = false23     order.append(node)24   }25   func addEdge(_ from: Int,_ to: Int){26     graph[from].nodes.append(to)27   }28     func findOrder(_ numCourses: Int,_ prerequisites: [[Int]]) -> [Int] {29       for i in 0...numCourses - 1{30         graph.append(Node())31         isInStack.append(false)32       }33       var from : Int?34       var to : Int?35       for edge in prerequisites {36         from = edge[0]37         to = edge[1]38         addEdge(from!,to!)39       }40       for i in 0...numCourses - 1 {41         if !graph[i].isSeen{42           dfs(i)43         }44       }45       if graphHasCycle {46         return []47       }48       return order49     }50 }