leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2115.cpp (1390B)

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