Contents

# Problem

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

 ``````1 2 3 4 `````` ``````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

 ``````1 2 3 4 5 `````` ``````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. ``````

## example 3

 ``````1 2 3 4 `````` ``````4 [[2,0],[1,0],[3,1],[3,2],[1,3]] Output: false ``````

## 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

## DFS

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````func canFinish(numCourses int, prerequisites [][]int) bool { m := make(map[int][]int, numCourses+1) for idx:= range prerequisites { if _, ok := m[prerequisites[idx][0]]; !ok { m[prerequisites[idx][0]] = make([]int,0) } m[prerequisites[idx][0]] = append(m[prerequisites[idx][0]], prerequisites[idx][1]) } for idx := range m { if !helper(m,idx, map[int]int{}) { return false } } return true } func helper( m map[int][]int, idx int, v map[int]int) bool { if _, ok := v[idx]; ok { return false } v[idx] = 1 for jdx := range m[idx] { if !helper(m, m[idx][jdx], v){ return false } delete(v, m[idx][jdx]) } return true } ``````