DFS cycle detection based on coloring the recursive path as "in progress" or not. If we get back to an "in progress" vertex, it's a part of a cycle.
(numCourses int, prerequisites [][]int)
| 63 | // DFS cycle detection based on coloring the recursive path as "in progress" |
| 64 | // or not. If we get back to an "in progress" vertex, it's a part of a cycle. |
| 65 | func canFinishDFS(numCourses int, prerequisites [][]int) bool { |
| 66 | if len(prerequisites) == 0 { |
| 67 | return true |
| 68 | } |
| 69 | |
| 70 | adjList := make(map[int][]int) |
| 71 | for _, pre := range prerequisites { |
| 72 | adjList[pre[0]] = append(adjList[pre[0]], pre[1]) |
| 73 | } |
| 74 | |
| 75 | // find if there is a cycle in the prerequisite dependency graph |
| 76 | for k := range adjList { |
| 77 | if hasCycleDFS(adjList, make([]int, numCourses), k) { |
| 78 | return false |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | return true |
| 83 | } |
| 84 | |
| 85 | func hasCycleDFS(adjList map[int][]int, colors []int, course int) bool { |
| 86 | // if this node is an ancestor of the DFS path taken, there is a cycle |