Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1年前 (2024/10/25 01:27)推噓0(0推 0噓 0→)

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 好爽喔字未提 -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg