2025.10.23学习日记

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new ArrayList[numCourses];
        //三色标记法 0 没学过 1 正在学 2 已学过
        int[] learned = new int[numCourses];
        Arrays.setAll(g , i -> new ArrayList<>());
        for(int[] p : prerequisites){
            int stu = p[0];
            int dep = p[1];
            g[stu].add(dep);
        }
        for(int i = 0 ; i < numCourses ; ++i){
            if(learned[i] == 0 && dfs(g,learned,i)){
                return false;
            }
        }
        return true;

    }
    //判断是否有环 有的话直接返回true
    private boolean dfs(List<Integer>[] g , int[] learned , int i ){
        if(learned[i] == 1){
            return true;
        }
        learned[i] = 1;
        boolean flag = false;
        for(Integer num : g[i]){
            if(learned[num] == 1 || learned[num] == 0 && dfs(g,learned,num)){
                return true;
            }
        }
        learned[i] = 2;
        return false;
    }
}