May Leetcode Challenge - Day 29

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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 list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

• The input prerequisites is a graph represented by a list 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.
• 1 <= numCourses <= 10^5

Solution

Build graph
Use dfs to find circulation nodes (pass more than one time)

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var graph = [Int: Set<Int>]()
    
        for pre in prerequisites {
            var next = graph[pre[1]] ?? []
            next.insert(pre[0])
            graph[pre[1]] = next
        }
        
        var states = Array(repeating: 0, count: numCourses)
        
        func dfs(_ v: Int) -> Bool {
            if states[v] == 1 { return false } //already pass one
            if states[v] == -1 { return true } //pass second times
            
            states[v] = -1
            for next in (graph[v] ?? []) {
                if dfs(next) {
                    return true
                }
            }
            states[v] = 1
            return false
        }
        
        for i in 0..<numCourses {
            if dfs(i) { return false }
        }
        
        return true
    }
}