1462. Course Schedule IV

 一刷 05/2022

Version #1 Topological Sort

Time O(E + V)

Space O(E + V)

Runtime: 124 ms, faster than 26.97% of Java online submissions for Course Schedule IV.

Memory Usage: 70.2 MB, less than 58.24% of Java online submissions for Course Schedule IV.

class Solution {

    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {

        Set<Integer>[] graph = new HashSet[numCourses];

        int[] indegree = new int[numCourses];

        Set<Integer>[] preReq = new HashSet[numCourses];

        for (int i = 0; i < numCourses; i++) {

            graph[i] = new HashSet<>();

            preReq[i] = new HashSet<>();

        }

        for (int[] prerequisite : prerequisites) {

            int from = prerequisite[0];

            int to = prerequisite[1];

            graph[from].add(to);

            indegree[to]++;

        }

        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < numCourses; i++) {

            if (indegree[i] == 0) {

                que.offer(i);

            }

        }

        

        while (!que.isEmpty()) {

            Integer curr = que.poll();

            for (int next : graph[curr]) {

                preReq[next].add(curr);

                preReq[next].addAll(preReq[curr]);

                indegree[next]--;

                if (indegree[next] == 0) {

                    que.offer(next);

                }

            }

        }

        List<Boolean> result = new ArrayList<>();

        for (int[] query : queries) {

            if (preReq[query[1]].contains(query[0])) {

                result.add(true);

            } else {

                result.add(false);

            }

        }

        return result;

    }

}