Course Schdule

lc 207

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all the courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. 0 is fatehr So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

bfs

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] degree = new int[numCourses];
        Queue queue = new LinkedList();
        int count=0;

        for(int i=0;i<numCourses;i++)
            graph[i] = new ArrayList();

        for(int i=0; i<prerequisites.length;i++){
            //后面课＋＋；
            degree[prerequisites[i][0]]++;
            //父亲数组
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        for(int i=0; i<degree.length;i++){
            if(degree[i] == 0){
                queue.add(i);
                count++;
            }
        }

        while(queue.size() != 0){
            int course = (int)queue.poll();
            for(int i=0; i<graph[course].size();i++){
                int pointer = (int)graph[course].get(i);
                degree[pointer]--;
                if(degree[pointer] == 0){
                    queue.add(pointer);
                    count++;
                }
            }
        }
        if(count == numCourses)
            return true;
        else    
            return false;
    }

dfs

       public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();

            boolean[] visited = new boolean[numCourses];
            for(int i=0; i<prerequisites.length;i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }

            for(int i=0; i<numCourses; i++){
                if(!dfs(graph,visited,i))
                    return false;
            }
            return true;
        }

        private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
            if(visited[course])
                return false;
            else
                visited[course] = true;;

            for(int i=0; i<graph[course].size();i++){
                if(!dfs(graph,visited,(int)graph[course].get(i)))
                    return false;
            }
            visited[course] = false;
            return true;
        }

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0|| prerequisites[0].length == 0) return true;
        Map<Integer, Integer> rMap = new HashMap<>();
        Map<Integer, List<Integer>> nextMap = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0 ; i < prerequisites.length; i++ ) {
            if (!rMap.containsKey(prerequisites[i][0])) {
                rMap.put(prerequisites[i][0], 0);
            }
            rMap.put(prerequisites[i][0], rMap.get(prerequisites[i][0]) + 1);
            if (!nextMap.containsKey(prerequisites[i][1])) {
                nextMap.put(prerequisites[i][1], new ArrayList<>());
            }
            List<Integer> next = nextMap.get(prerequisites[i][1]);
            next.add(prerequisites[i][0]);
            nextMap.put(prerequisites[i][1], next);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!rMap.containsKey(i)) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            Integer cur = queue.poll();
            if (!nextMap.containsKey(cur)) {
                continue;
            }
            for (Integer i : nextMap.get(cur)) {
                if (rMap.get(i) == 1) {
                    rMap.remove(i);
                    queue.offer(i);
                } else {
                    rMap.put(i, rMap.get(i) - 1);
                }
            }
        }
        return rMap.size() == 0;
    }
}