Possibility of finishing all courses given pre-requisites
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| int Solution::solve(int A, vector<int> &B, vector<int> &C) { unordered_map<int,int> ind; unordered_map<int,vector<int>> adj; for(int i = 0; i < B.size(); i++) { ind[C[i]]++; ind[B[i]] += 0; adj[B[i]].push_back(C[i]); } queue<int> q; for(auto [k,v] : ind) { if(v == 0) q.push(k); } while(q.size()) { int u = q.front(); q.pop(); for(auto v : adj[u]) { if(--ind[v] == 0) { q.push(v); } } } for(auto [k,v] : ind) if(v) return false; return true; }
|