Course Schedule II

LC 210

return the possible solutions

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses == 0) return new int[0];
        int[] res = new int[numCourses];
        if(prerequisites == null || prerequisites.length == 0 || prerequisites[0] == null || prerequisites[0].length == 0){
            for(int i = 0; i < numCourses; i++){
                res[i] = i;
            }
            return res;
        }
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        int[] degree = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){
            if(map.containsKey(prerequisites[i][1])){
                map.get(prerequisites[i][1]).add(prerequisites[i][0]);
                degree[prerequisites[i][0]]++;
            }else{
                List<Integer> list = new ArrayList<Integer>();
                list.add(prerequisites[i][0]);
                map.put(prerequisites[i][1], list);
                degree[prerequisites[i][0]]++;
            }
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++){
            if(degree[i] == 0 ){
                queue.offer(i);
            }
        } 
        int count = 0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            res[count++] = cur;
            if(map.containsKey(cur)){
                for(int item : map.get(cur)){
                    degree[item]--;
                    if(degree[item] == 0){
                        queue.offer(item);
                    }
                }
            }
        }
        if(count != numCourses) return new int[0];
        return res;
    }
}

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Integer> rMap = new HashMap<>();
        Map<Integer, List<Integer>> nextMap = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        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();
            list.add(cur);
            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);
                }
            }
        }
        if (rMap.size() != 0) {
            return new int[0];
        }
        return list.stream().mapToInt(i -> i).toArray();
    }
}