leetcode-go/leetcode/medium/207.course-schedule.go

// Will visit, visiting, visited
const (
	WILL = iota
	ING
	ED
)

func canFinish(numCourses int, prerequisites [][]int) bool {
	adj := make([][]bool, numCourses)
	for i := range adj {
		adj[i] = make([]bool, numCourses)
	}
	for i := range prerequisites {
		adj[prerequisites[i][0]][prerequisites[i][1]] = true
	}
	tag := make([]int, numCourses)
	hasRing := false
	for i := 0; i < numCourses; i++ {
		dfs(i, adj, &tag, &hasRing)
		if hasRing {
			return false
		}
	}
	return true
}

func dfs(x int, adj [][]bool, tag *[]int, hasRing *bool) {
	if *hasRing || (*tag)[x] == ED {
		return
	}
	(*tag)[x] = ING
	for i := range adj[x] {
		if !adj[x][i] {
			continue
		}
		if (*tag)[i] == WILL {
			dfs(i, adj, tag, hasRing)
		} else if (*tag)[i] == ING {
			*hasRing = true
			return
		}
	}
	(*tag)[x] = ED
}