c++ | bitset
Idea\nFor every person who can\'t talk with its friend, store which language he/she needs to be taught and store the frequency of that language in an array toTe
<b>Idea</b>\nFor every person who can\'t talk with its friend, store which language he/she needs to be taught and store the frequency of that language in an array `toTeach`. The language that needs to be taught to minimum number of people is the desired one. \nNote: In order to ensure that the same person to be taught is not counted twice, we maintain a `visited` array.\n```\nclass Solution {\npublic:\nint minimumTeachings(int n, vector<vector<int>>& lng, vector<vector<int>>& ar){\n    // n-> languages\n    // m-> users\n    int m=lng.size(),ct=(1<<30);\n    bool *vis=new bool[m]();\n    int *toTeach = new int[n]();\n    vector<bitset<501>> v;\n    for(auto it:lng){\n        bitset<501> tmp;\n        for(auto it1:it) tmp.set(it1-1);\n        v.push_back(tmp);\n    }\n    for(auto it:ar){\n        if( (v[it[0]-1] & v[it[1]-1]).count()){\n            // they can talk\n        }else{\n            for(int i=0;i<n;i++){\n                if(!(v[it[0]-1].test(i)) && !vis[it[0]-1]) toTeach[i]++;\n                if(!(v[it[1]-1].test(i)) && !vis[it[1]-1]) toTeach[i]++;\n            }\n            vis[it[0]-1]=true,vis[it[1]-1]=true;\n        }\n    }\n    for(int i=0;i<n;i++) ct=min(ct,toTeach[i]);\n    if(ct==(1<<30)) return 0;\n    return ct;\n}\n};\n```
[]