// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func canFinishCourses(numCourses int, array [][]int) bool {
	graph := map[int][]int{}
	for _, pre := range array {
		graph[pre[0]] = append(graph[pre[0]], pre[1])
	}

	traced := map[int]bool{}
	visited := map[int]bool{}

	for i := 0; i < numCourses; i++ {
		if hasCycle(i, graph, traced, visited) {
			return false
		}
	}

	return true
}

func hasCycle(course int, graph map[int][]int, traced, visited map[int]bool) bool {
	if traced[course] {
		return true
	}

	if visited[course] {
		return false
	}

	traced[course] = true

	for _, pre := range graph[course] {
		if hasCycle(pre, graph, traced, visited) {
			return true
		}
	}

	traced[course] = false
	visited[course] = true

	return false
}

func main() {
	array := [][]int{{1, 2}, {0, 2}}
	res := canFinishCourses(2, array)
	fmt.Println(res)
}

//$ go run interview5-2.go
//true