207. 课程表

完全考察拓扑排序的。

 //拓扑
    public int[] canFinish1(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] lists = new ArrayList[numCourses];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int[] temp = prerequisites[i];
            if (lists[temp[1]] == null) {
                lists[temp[1]] = new ArrayList<>();
            }
            ArrayList<Integer> list = lists[temp[1]];
            list.add(temp[0]);
        }
        int[] indegrees = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            indegrees[prerequisites[i][0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if(indegrees[i] == 0) {
                queue.add(i);
            }
        }
        int num = 0;
        while (!queue.isEmpty()) {
            int index = queue.poll();
            ArrayList<Integer> list = lists[index];
            num++;
            for (int i = 0; i < list.size(); i++) {
                int next = list.get(i);

                if(--indegrees[next] == 0) {
                    queue.add(next);
                }
            }
        }
        return new int[]{1,2};
    }
    //dfs
    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] lists = new ArrayList[numCourses];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int[] temp = prerequisites[i];
            if (lists[temp[1]] == null) {
                lists[temp[1]] = new ArrayList<>();
            }
            ArrayList<Integer> list = lists[temp[1]];
            list.add(temp[0]);
        }
        int[] indegrees = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if(!dfs(lists, indegrees, i)) {
                return false;
            }
        }
        return true;
    }

    public boolean dfs(ArrayList<Integer>[] map, int[] indegrees, int cur) {
        if(indegrees[cur] == 1) {
            return false;
        }
        if(indegrees[cur] == 2) {
            return true;
        }
        indegrees[cur] = 1;
        ArrayList<Integer> nexts = map[cur];
        for (int i = 0; i < nexts.size(); i++) {
            if(!dfs(map, indegrees, nexts.get(i))) {
                return false;
            }
        }
        indegrees[cur] = 2;
        return true;
    }