Advertisement
HXXXXJ

207. Course Schedule

Feb 21st, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Swift 1.19 KB | None | 0 0
  1.        func canFinish(_ n: Int, _ prerequisites: [[Int]]) -> Bool {
  2.         var adjentMap = [Int: Set<Int>]()
  3.         var indegree = [Int](repeating: 0 , count: n)
  4.  
  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 list = adjentMap[first]{
  11.                 newSet = list  
  12.             }else {
  13.                 newSet = Set<Int>()                        
  14.             }
  15.             newSet.insert(second)
  16.             adjentMap[first] = newSet
  17.         }
  18.         var queue = [Int]()
  19.         for i in 0 ..< n  {
  20.             if indegree[i] == 0{
  21.                 queue.append(i)
  22.             }
  23.         }
  24.         var count = 0
  25.         while !queue.isEmpty {
  26.             count += 1
  27.             let cur = queue.removeFirst()
  28.             if let courseSet = adjentMap[cur] {
  29.                 for adj in courseSet {
  30.                     indegree[adj] -= 1
  31.                     if indegree[adj] == 0{
  32.                         queue.append(adj)
  33.                     }
  34.                 }
  35.             }
  36.         }
  37.        
  38.         return count == n
  39.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement