course-schedule-iv.cpp (2031B)
1 class Solution { 2 public: 3 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) { 4 // must take numcourses 5 // 0 -> numCourses - 1 6 // prereq[i] = [a_i,b_i] must take a_i before b_i 7 // queries[j] = [u_j, v_j] you have to answer if u_j is a pre-req for v_j 8 // this can be a transitive pre-req too 9 // return answer where answer[j] answers queries[j] 10 // prereqs has no cycles 11 12 // idea: 13 // realize the entire dependency chain 14 // this would require a bunch of memory, but is possible 15 // O(n^2) specifically where n is the number of courses 16 // course count is <= 100 though so at most there'd be ~10,000 edges 17 18 // bool vectors are spooky so 1 == true, 0 == false 19 vector<vector<int>> isReachable{}; 20 21 22 // how? 23 // do bfs from each node 24 25 vector<vector<int>> dependencies(numCourses); 26 27 for(auto pre: prerequisites) { 28 dependencies[pre[0]].push_back(pre[1]); 29 } 30 31 for(int i = 0; i < numCourses; ++i) { 32 isReachable.push_back( bfs(numCourses, dependencies, i) ); 33 } 34 35 vector<bool> answer{}; 36 for(auto query: queries) { 37 answer.push_back(isReachable[query[0]][query[1]] == 1); 38 } 39 40 return answer; 41 } 42 private: 43 vector<int> bfs(int courses, vector<vector<int>>& dependencies, int current) { 44 vector<int> stack{}; 45 vector<int> result(courses); 46 47 stack.push_back(current); 48 49 while(stack.size() > size_t{0}) { 50 int idx = stack.back(); 51 stack.pop_back(); 52 result[idx] = 1; 53 for(auto req: dependencies[idx]) { 54 if(result[req] == 0) { 55 stack.push_back(req); 56 } 57 } 58 } 59 60 return result; 61 } 62 63 };