leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2115.cpp (1390B)

0 class Solution { 1 const int SIZE = 101; 2 3 public: 4 vector<string> findAllRecipes(vector<string> &recipes, vector<vector<string>> &ingredients, 5 vector<string> &supplies) { 6 unordered_map<string, int> hash; 7 unordered_set<string> us(supplies.begin(), supplies.end()); 8 vector<vector<int>> adj(SIZE); 9 vector<int> count(SIZE); 10 vector<string> finished; 11 12 for (int i = 0; i < recipes.size(); i++) 13 hash.insert({recipes[i], i}); 14 for (int i = 0; i < recipes.size(); i++) { 15 for (string &s : ingredients[i]) 16 if (!us.count(s)) { 17 count[i]++; 18 if (!hash.count(s)) 19 count[i] = INT_MAX; 20 else 21 adj[hash[s]].push_back(i); 22 } 23 } 24 25 queue<int> q; 26 for (int i = 0; i < recipes.size(); i++) { 27 if (!count[i]) { 28 q.push(i); 29 finished.push_back(recipes[i]); 30 } 31 } 32 33 while (!q.empty()) { 34 int root = q.front(); 35 q.pop(); 36 for (int c : adj[root]) { 37 if (!--count[c]) { 38 q.push(c); 39 finished.push_back(recipes[c]); 40 } 41 } 42 } 43 44 return finished; 45 } 46 };