[c++ 200ms 100%] bitset
1  Use bitset to represent the  languages of a user (bitset is very similar to a mask)\n2  Use bitset to test if two users has common langue, if not, we mark th
1  Use bitset to represent the  languages of a user (bitset is very similar to a mask)\n2  Use bitset to test if two users has common langue, if not, we mark the two user as candidate ( has at least one friend he can not talk to). \n    Here we want to exclude all users that have no issue to talk to his/her friends.\n3  For all users candidate,  we caculate the usage count of each language. \n\n4  The answer is min(users candidate count - usage count of one language). \n    In another way, among all users involved, the language used by most user candidates is the language we choose.\n   \n\nTime : m * n\n\n```\nclass Solution {\npublic:\n    int n;\n    int m;\n     vector<bitset<501>> dp;\n    int minimumTeachings(int n1, vector<vector<int>>& languages, vector<vector<int>>& friendships) {\n        n = n1;\n        m = languages.size();\n        dp.resize(m + 1);\n        for (int i =0; i < m; i++)\n        {\n            for (auto& l : languages[i])\n            {\n                dp[i + 1][l] = 1;\n            }\n        }\n        \n        vector<int> candicate(m + 1, 0);\n        for (auto& v : friendships)\n        {\n            bitset<501> un = dp[v[0]] & dp[v[1]];\n            if (un.count() == 0)\n            {\n                //nospeakfrieds.push_back(v);\n                candicate[v[0]] = 1;\n                candicate[v[1]] = 1;\n            }\n        }\n        vector<int> ldp(n + 1, 0);\n        int cnt = 0;\n        for (int i = 1; i <= m; i++)\n        {\n            if (candicate[i] == 1)\n            {\n                cnt++;\n                for (auto& l : languages[i-1])\n                {\n                    ldp[l]++;\n                }\n            }\n        }\n        int res = cnt;\n        //cout << cnt << endl;\n        for (int i = 1; i <= n; i++)\n        {\n            //cout << i << "," << ldp[i] << endl;\n            res = min(res, cnt - ldp[i]);\n        }\n        return res;\n    }\n};\n```
[]