Course Schedule II

Java

public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // write your code here
        int[] result = new int[numCourses];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] degree = new int[numCourses];
        for (int [] p : prerequisites) {
            if (!map.containsKey(p[1]) || !map.get(p[1]).contains(p[0])) {
                degree[p[0]]++;
            }
            map.putIfAbsent(p[1], new HashSet<>());
            map.get(p[1]).add(p[0]);
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) {
                queue.offer(i);
            }
            // System.out.println(degree[i]);
        }
    
        
        int i = 0;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result[i] = current;
            i++;
            if (!map.containsKey(current)) {
                continue;
            }
            
            for (int course : map.get(current)) {
                degree[course]--;
                if (degree[course] == 0) {
                    queue.offer(course);
                }
            }
        }
        // System.out.println(unSelected);
        return i == numCourses ? result : new int[0];
    }
}

Python

def findOrder(self, numCourses, prerequisites):
    dic = {i: set() for i in xrange(numCourses)}
    neigh = collections.defaultdict(set)
    for i, j in prerequisites:
        dic[i].add(j)
        neigh[j].add(i)
    # queue stores the courses which have no prerequisites
    queue = collections.deque([i for i in dic if not dic[i]])
    count, res = 0, []
    while queue:
        node = queue.popleft()
        res.append(node)
        count += 1
        for i in neigh[node]:
            dic[i].remove(node)
            if not dic[i]:
                queue.append(i)
    return res if count == numCourses else []