leetcodeSolution to some Leetcode problems written in C++ |
| git clone git://git.dimitrijedobrota.com/leetcode.git |
| Log | Files | Refs | README | LICENSE |
1462.cpp (2904B)
0 // DFS 1 class Solution { 2 public: 3 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, 4 vector<vector<int>> &queries) { 5 vector<vector<int>> adj(numCourses); 6 vector<unordered_set<int>> pre(numCourses); 7 8 for (auto &p : prerequisites) 9 adj[p[0]].push_back(p[1]); 10 11 for (int i = 0; i < numCourses; i++) { 12 unordered_set<int> visited; 13 stack<int> st; 14 st.push(i); 15 visited.insert(i); 16 while (!st.empty()) { 17 int crnt = st.top(); 18 st.pop(); 19 for (int &c : adj[crnt]) { 20 if (visited.count(c)) continue; 21 visited.insert(c); 22 pre[c].insert(i); 23 st.push(c); 24 } 25 } 26 } 27 28 vector<bool> res; 29 for (auto &p : queries) 30 res.push_back(pre[p[1]].count(p[0])); 31 return res; 32 } 33 }; 34 35 // Topological sort with dependency propagation 36 class Solution { 37 public: 38 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, 39 vector<vector<int>> &queries) { 40 vector<unordered_set<int>> pre(numCourses); 41 vector<vector<int>> adj(numCourses); 42 vector<int> count(numCourses); 43 44 for (auto &p : prerequisites) { 45 adj[p[0]].push_back(p[1]); 46 count[p[1]]++; 47 } 48 49 queue<int> q; 50 for (int i = 0; i < numCourses; i++) 51 if (!count[i]) q.push(i); 52 53 while (!q.empty()) { 54 int crnt = q.front(); 55 q.pop(); 56 for (int &c : adj[crnt]) { 57 pre[c].insert(crnt); 58 pre[c].insert(pre[crnt].begin(), pre[crnt].end()); 59 if (!--count[c]) q.push(c); 60 } 61 } 62 63 vector<bool> res; 64 for (auto &p : queries) 65 res.push_back(pre[p[1]].count(p[0])); 66 return res; 67 } 68 }; 69 70 // Topological sort using bitseclass Solution { 71 public: 72 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, 73 vector<vector<int>> &queries) { 74 vector<bitset<100>> pre(numCourses); 75 vector<vector<int>> adj(numCourses); 76 vector<int> count(numCourses); 77 78 for (auto &p : prerequisites) { 79 adj[p[0]].push_back(p[1]); 80 count[p[1]]++; 81 } 82 83 queue<int> q; 84 for (int i = 0; i < numCourses; i++) 85 if (!count[i]) q.push(i); 86 87 while (!q.empty()) { 88 int crnt = q.front(); 89 q.pop(); 90 for (int &c : adj[crnt]) { 91 pre[c].set(crnt); 92 pre[c] |= pre[crnt]; 93 if (!--count[c]) q.push(c); 94 } 95 } 96 97 vector<bool> res; 98 for (auto &p : queries) 99 res.push_back(pre[p[1]][p[0]]); 100 return res; 101 } 102 } 103 ;