Intersection of common languages
Very unclear description, I must say...\nBut not a bad question after all.\n\ncpp\n// check if user u and v share a common language.\n// sorted array and two-po
Very unclear description, I must say...\nBut not a bad question after all.\n\n```cpp\n// check if user u and v share a common language.\n// sorted array and two-pointer, \n// binary search might be even better.\nbool haveCommon(vector<vector<int>>& lan, int u, int v)\n{\n\tint i = 0;\n\tint j = 0;\n\t\n\twhile (i < lan[u].size() && j < lan[v].size())\n\t{\n\t\tif (lan[u][i] < lan[v][j])\n\t\t\t++ i;\n\t\telse if (lan[u][i] > lan[v][j])\n\t\t\t++ j;\n\t\telse\n\t\t\treturn true;\n\t}\n\t\n\treturn false;\n}\n\nint minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {\n\tint m = languages.size();\n\tvector<int> lan(n + 1);\n\tqueue<int> que;\n\tset<int> learner;\n\t\n\t// sorted, might not be necessary, but we better not relay to much on input data.\n\tfor (auto &l : languages)\n\t\tsort(begin(l), end(l));\n\t\n\t// for each friendship between u and v,\n\tfor (auto &f : friendships)\n\t{\n\t\tint u = f[0] - 1;\n\t\tint v = f[1] - 1;\n\t\t\n\t\t// if they don\'t share a common language, \n\t\tif (! haveCommon(languages, u, v))\n\t\t{\n\t\t\t// check if user u has already be considered, \n\t\t\t// if not,\n\t\t\tif (learner.count(u) == 0)\n\t\t\t{\n\t\t\t\t// put user u into the set that must be taugh a new language.\n\t\t\t\tlearner.insert(u);\n\t\t\t\t\n\t\t\t\t// record those languages that the user u has alreay known.\n\t\t\t\tfor (auto l : languages[u])\n\t\t\t\t\t++ lan[l];\n\t\t\t}\n\t\t\t\n\t\t\t// apply same logic to user v.\n\t\t\tif (learner.count(v) == 0)\n\t\t\t{\n\t\t\t\tlearner.insert(v);\n\t\t\t\tfor (auto l : languages[v])\n\t\t\t\t\t++ lan[l];\n\t\t\t}\n\t\t}\n\t}\n\t\n\t// inside the set are the total users that must learn at least one language \n\t// to fulfill the communication between some of their friendship.\n\t// and we also have records of the summary of how many users already known which language.\n\t// find the dominate language, and those who do know this language must learn it, \n\t// so that each user inside the set know this dominate language.\n\treturn learner.size() - *max_element(begin(lan), end(lan));\n}\n```\n
['C']