Leetcode1462-课程表 IV

拓扑排序+集合合并

        整个课程表就是一个有向无环图，我们在对它进行拓扑排序的同时，对每个课程维护一个集合，集合里面存放的是这个课程的先决条件；对于某个课程的直接子课程，我们把它的集合合并到子课程的集合中去，这样我们可以在平均复杂度为O（1），最坏复杂度为O（n）的情形下来回答每个询问。

class Solution {
public:
    vector<bool> checkIfPrerequisite(int numCourses, vectorint>>& prerequisites, vectorint>>& queries) {
        vectorint>> p(numCourses);
        vector<bool> ans(queries.size());
        vector<int> e[numCourses];
        vector<int> deg(numCourses,0);
        for(auto t:prerequisites){
            e[t[0]].push_back(t[1]);
            deg[t[1]]++;
        }
        queue<int> q;
        for(int i=0;i
            if(!deg[i]) q.push(i);
        }
        while(!q.empty()){
            auto x=q.front();
            q.pop();
            for(auto y:e[x]){
                p[y].insert(x);
                for(auto g:p[x]) p[y].insert(g);
                if(!--deg[y]) q.push(y);
            }
        }
        for(int i=0;isize();i++){
            ans[i]=p[queries[i][1]].count(queries[i][0]);
        }
        return ans;
    }
};

时间复杂度：平均O（n+m+q），最坏O（n^2+nm+nq），n为点数，m为边数，q为询问数

空间复杂度：O（n^2）最坏情况整个图为一条链