LeetCode -- 1462. 课程表 IV （拓扑排序，二进制集合）

class Solution {
public:

    const static int N = 110, M = N * N;

    int h[N], e[M], ne[M], idx;
    int din[N], q[N];

    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }

    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        memset(h, -1, sizeof h);
        vector<bitset<110>> pre(numCourses, 0);
        for(auto &it : prerequisites) {
            add(it[0], it[1]);
            din[it[1]] ++ ;
            pre[it[1]].set(it[0]);
        }

        int hh = 0, tt = -1;
        for(int i = 0; i < numCourses; i ++ ) {
            if(!din[i]) q[ ++ tt] = i;
        }

        while(hh <= tt) {
            int t = q[hh ++ ];
            for(int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                pre[j] |= pre[t];
                if( -- din[j] == 0) q[ ++ tt] = j;
            }
        }
        vector<bool> res;
        for(auto &it : queries) {
            res.push_back(pre[it[1]][it[0]]);
        }

        return res;
    }
};