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
好爽喔字未提