package courseschedule

func visit(prereqs map[int][]int, temporary map[int]bool, permanent map[int]bool, class int) bool {
	if temporary[class] {
		return false
	}
	if permanent[class] {
		return true
	}

	if _, ok := prereqs[class]; !ok {
		return true
	}

	temporary[class] = true

	for _, p := range prereqs[class] {
		if !visit(prereqs, temporary, permanent, p) {
			return false
		}
	}

	permanent[class] = true
	temporary[class] = false

	return true
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	prereqs := map[int][]int{}
	for _, p := range prerequisites {
		class, prerequisite := p[0], p[1]

		if _, ok := prereqs[class]; !ok {
			prereqs[class] = []int{}
		}

		prereqs[class] = append(prereqs[class], prerequisite)
	}

	temporary, permanent := map[int]bool{}, map[int]bool{}
	for c := range prereqs {
		if permanent[c] {
			continue
		}

		if !visit(prereqs, temporary, permanent, c) {
			return false
		}
	}

	return true
}