leetcode

0 class Solution {

1 public:

2 vector<int> peopleIndexes(const vector<vector<string>> &favoriteCompanies) const {

3 const int n = size(favoriteCompanies);

4 vector<unordered_set<int>> companies(n);

5 unordered_map<string, int> um;

6

7 for (int i = 0; i < n; i++) {

8 for (const auto &company : favoriteCompanies[i]) {

9 const auto it = um.find(company);

10 const int key = it == um.end() ? um.size() : it->second;

11 if (it == um.end()) um.emplace(company, key);

12 companies[i].insert(key);

13 }

14 }

15

16 static int candidates[101];

17 vector<int> res;

18 for (int i = 0; i < n; i++) {

19 int elems = 0;

20 for (int j = 0; j < n; j++) {

21 if (i == j) continue;

22 if (size(companies[i]) >= size(companies[j])) continue;

23 candidates[elems++] = j;

24 }

25

26 for (const auto &company : companies[i]) {

27 int t = 0;

28 for (int j = 0; j < elems; j++) {

29 const int candidate = candidates[j];

30 if (companies[candidate].count(company)) {

31 candidates[t++] = candidate;

32 }

33 }

34

35 if (!t) {

36 res.push_back(i);

37 break;

38 }

39 elems = t;

40 }

41 }

42 return res;

43 }

44 };