course_schedule.go

package course_schedule

// BFS
funccanFinish(numCoursesint, prerequisites [][]int) bool {
graph:=map[int][]int{}
inDegree:=make([]int, numCourses)
fori:=rangeprerequisites {
graph[prerequisites[i][1]] =append(graph[prerequisites[i][1]], prerequisites[i][0])
inDegree[prerequisites[i][0]]++
 }
queue:= []int{}
fori:=rangeinDegree {
ifinDegree[i] ==0 {
queue=append(queue, i)
 }
 }
forlen(queue) !=0 {
head:=queue[0]
queue=queue[1:]
fori:=rangegraph[head] {
inDegree[graph[head][i]]--
ifinDegree[graph[head][i]] ==0 {
queue=append(queue, graph[head][i])
 }
 }
 }
fori:=rangeinDegree {
ifinDegree[i] !=0 {
returnfalse
 }
 }
returntrue
}

// DFS
funccanFinishDFS(numCoursesint, prerequisites [][]int) bool {
graph:=map[int][]int{}
fori:=rangeprerequisites {
graph[prerequisites[i][1]] =append(graph[prerequisites[i][1]], prerequisites[i][0])
 }
path:=make([]bool, numCourses)
visited:=make([]bool, numCourses)
fori:=0; i<numCourses; i++ {
ifvisited[i] {
continue
 }
ifhasCycle(i, graph, path, visited) {
returnfalse
 }
 }
returntrue
}

funchasCycle(startint, graphmap[int][]int, path []bool, visited []bool) bool {
fori:=rangegraph[start] {
ifvisited[graph[start][i]] {
continue
 }
ifpath[graph[start][i]] {
returntrue
 }
path[graph[start][i]] =true
ifhasCycle(graph[start][i], graph, path, visited) {
returntrue
 }
path[graph[start][i]] =false
 }
visited[start] =true
returnfalse
}