Joey LIU | NANTSOU


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Use topological sort
 * non-dag would not be in queue so that taken would not equal to numCourses
 */
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        }
        int[] indegree = new int[numCourses];
        Map<Integer, List<Integer>> mem = new HashMap<>();
        for (int[] p:prerequisites) {
            indegree[p[0]]++;
            if (!mem.containsKey(p[1])) {
                mem.put(p[1], new ArrayList<Integer>());
            }
            mem.get(p[1]).add(p[0]);
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
        
        int taken = 0;
        while (!q.isEmpty()) {
            int v = q.poll();
            taken++;
            if (mem.containsKey(v)) {
                List<Integer> uList = mem.get(v);
                for (int u:uList) {
                    indegree[u]--;
                    if (indegree[u] == 0) {
                        q.offer(u);
                    }
                }
            }
        }
        return taken == numCourses;
    }
}