leetcode

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 };