No DP, C++ Graph Solution using BFS
I looked in the discuss section and found that almost everyone has done it using dp with bitmasking. However I was able to visualize it as graph. Do upvote me i
I looked in the discuss section and found that almost everyone has done it using dp with bitmasking. However I was able to visualize it as graph. Do upvote me if you like it.\n\nclass Solution {\npublic:\n   \n    unordered_map<string, int> mp;\n   \n    vector<int> smallestSufficientTeam(vector<string>& skills, vector<vector<string>>& people) {\n        \n        int n = skills.size();\n        int i = 0;\n        \n        for(string s: skills)\n            mp[s] = i++;\n            \n         int m = people.size();\n        \n         vector<int> masks(m+1, 0);\n        \n         for(int i = 0; i < m; i++)\n             for(string s: people[i])\n                   masks[i+1] = masks[i+1] | (1 << mp[s]);\n             \n          queue< pair<int, int> > q;\n          vector< vector<bool> > vis(m+1, vector<bool>(1 << n, 0));\n          \n          pair<int, int> par[m+1][1 << n];\n        \n          for(int i = 0; i <= m; i++)\n              for(int j = 0; j < (1 << n); j++)\n                  par[i][j] = {0, 0};\n        \n          q.push({0, 0});\n          vis[0][0] = 1;\n          int fMask = (1 << n) - 1;\n          int x = 0;\n        \n          while(q.size())\n          {\n              auto pr = q.front();\n              q.pop();\n              \n              int p = pr.first;\n              int mask = pr.second;\n              \n              if(mask == fMask)\n              {\n                   x = p;\n                   break;\n              }\n             \n              for(int i = 1; i <= m; i++)\n                if(i != p)\n                   if(vis[i][mask | masks[i]] == 0)\n                   {\n                       vis[i][mask | masks[i]] = 1;\n                       par[i][mask | masks[i]] = {p, mask};\n                       q.push({i, mask | masks[i]});\n                   }\n              \n          }\n        \n         int cur = fMask;\n         vector<int> ans;\n         pair<int, int> net = {0, 0};\n        \n         while(1)\n         {\n             ans.push_back(x-1);\n             auto z = par[x][cur];\n             \n             x = z.first;\n             cur = z.second;\n             \n             if(z == net)\n                 break;\n         }\n       \n        return ans;    \n    }\n};
['Breadth-First Search', 'Graph']