1462. course schedule iv
昨天想说复习一下拓朴拉ㄐ兽
发现课程表竟然有4就写ㄌ
简单来说就是给你修课顺序
判断a课是不是b课的先修课程
##
没cycle所以是dag
做adj list
找source (indegree = 0
做一个reachable matrix ( suc
node i 可以到node j的话
mat[i][j] = true
back tracking, dp看过的点
因为suc 用bitset存所以跟child &up 就好
class Solution {
public:
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& q) {
vector<bitset<100>> suc(n);
vector<vector<int>> adj(n);
vector<int> indg(n, 0);
for(auto v: pre){
adj[v[0]].push_back(v[1]);
indg[v[1]]++;
}
bitset<100> seen = 0;
for(int i = 0; i < n; i++){
if(indg[i] == 0){
dfs(i, adj, suc, seen);
}
}
int len = q.size();
vector<bool> res(len);
for(int i = 0; i < len; i++){
res[i] = suc[ q[i][0] ][ q[i][1] ];
}
return res;
}
bitset<100> dfs(int idx, vector<vector<int>>& adj, vector<bitset<100>>& suc, bitset<100>& seen){
if(seen[idx]) return suc[idx];
seen[idx] = 1;
bitset<100> bs = 0;
for(int i: adj[idx]){
bs |= dfs(i, adj, suc, seen);
}
bs[idx] = 1;
suc[idx] = bs;
return bs;
}
};
solution好像都n*e
我开dp是不是只要n+e
好爽喔字未提