# 1462. Course Schedule IV
###### tags: `Leetcode` `BFS` `Topological Sort` `Medium`
Link: https://leetcode.com/problems/course-schedule-iv/
## 思路
一开始的想法是一个query一个query处理 虽然也可以accept 但跑的速度太慢了
后来改成先把每个课程的preCourse都存下来 之后再处理query 就快很多
## Code

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = defaultdict(set)
        countPre = [0]*numCourses
        for a, b in prerequisites:
            graph[a].add(b)
            countPre[b] += 1
        
        queue = []
        for i in range(numCourses):
            if countPre[i]==0:
                queue.append(i)
        
        pres = collections.defaultdict(set)
        while queue:
            curr = queue.pop(0)
            for nextCourse in graph[curr]:
                countPre[nextCourse] -= 1
                pres[nextCourse].add(curr)
                pres[nextCourse].update(pres[curr])
                if countPre[nextCourse]==0:
                    queue.append(nextCourse)
        
        ans = []
        for u, v in queries:
            ans.append(u in pres[v])
        return ans

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Set<Integer>> graph = new ArrayList<>();
        List<Set<Integer>> preCourse = new ArrayList<>();
        int[] numPreCourse = new int[numCourses+1];
        
        for(int i=0; i<numCourses; i++){
            graph.add(new HashSet<>());
            preCourse.add(new HashSet<>());
        }
        for(int[] pre:prerequisites){
            int prev = pre[0], next = pre[1];
            graph.get(pre[0]).add(pre[1]);
            numPreCourse[next]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<numCourses; i++){
            if(numPreCourse[i]==0) q.add(i);
        }
        
        while(!q.isEmpty()){
            int curr = q.poll();
            Set<Integer> currSet = preCourse.get(curr);
            for(int next:graph.get(curr)){
                preCourse.get(next).add(curr);
                preCourse.get(next).addAll(preCourse.get(curr));
                numPreCourse[next]--;
                if(numPreCourse[next]==0){
                    q.add(next);
                }
            }
        }
        
        List<Boolean> ans = new ArrayList<>();
        for(int i=0; i<queries.length; i++){
            int[] query = queries[i];
            int prev = query[0];
            int target = query[1];
            if(preCourse.get(target).contains(prev)) ans.add(true);
            else ans.add(false);
        }
        return ans;
    }
}