Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- func canFinish(_ n: Int, _ prerequisites: [[Int]]) -> Bool {
- var adjentMap = [Int: Set<Int>]()
- var indegree = [Int](repeating: 0 , count: n)
- for prerequisite in prerequisites{
- let first = prerequisite[1]
- let second = prerequisite[0]
- indegree[second] += 1
- var newSet:Set<Int>
- if let list = adjentMap[first]{
- newSet = list
- }else {
- newSet = Set<Int>()
- }
- newSet.insert(second)
- adjentMap[first] = newSet
- }
- var queue = [Int]()
- for i in 0 ..< n {
- if indegree[i] == 0{
- queue.append(i)
- }
- }
- var count = 0
- while !queue.isEmpty {
- count += 1
- let cur = queue.removeFirst()
- if let courseSet = adjentMap[cur] {
- for adj in courseSet {
- indegree[adj] -= 1
- if indegree[adj] == 0{
- queue.append(adj)
- }
- }
- }
- }
- return count == n
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement