Soyo

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] ?? []
next.insert(pre)
graph[pre] = 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
}
}
``````