[Python] - Commented and Simple Python Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nI think this problem is in the harder range of medium problems.\n\nThere are some thing
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI think this problem is in the harder range of medium problems.\n\nThere are some things you need to consider:\n1) We only deal with users that are disconnected from other users\n2) We need to keep track of the most common known language for each disconnected user\n3) While keeping track of the most common spoken language for each disconnected user, we should be careful to not count users multiple times if they appear in several disconnected friendships (both friends don\'t have a common language)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe do all of these things in one loop over the friendships, but first we convert all lists of languages to sets of languages to have a quicker way to compute intersections (i.e. finding whether two friends have a common language).\n\nAfter that we iterate over all friendships and immediately continue if two users have a common language and therefore are connected. We do this quickly using a set intersection.\n\nIf users are disconnected, we add their languages to a language counter, but in order to prevent us from counting the languages of a user multiple times (if he has multiple disconnected friendships), we keep track of these disconnected users in a set.\n\nFor the result we then take the most common language from all users and subtract its frequency from the amount of disconnected users. This gives ous the amount of users we would have to teach.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(K*N), where K is the amount of friendships and N is the amount of languages. The K comes from the loop and the N from the set intersection. \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) for the counter of languages and the set of visited disconnected users (also N at most).\n\n# Code\n```\nclass Solution:\n    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n\n        # make languages to a set for quick lookup\n        languages = [set(langi) for langi in languages]\n\n        # go through the friendships and check whether they can not communicate\n        # count the languages these users already know as well as keeping\n        # track which user we might have to teach in a visited set.\n        visited = set()\n        language_cn = collections.Counter()\n        for user1, user2 in friendships:\n\n            # check whether they already can communicate\n            if languages[user1-1].intersection(languages[user2-1]):\n                continue\n\n            # if we have not added the languages of a disconnected user\n            # we use them to keep track of languages disconnected users\n            # speek\n            if user1 not in visited:\n                language_cn.update(languages[user1-1])\n                visited.add(user1)\n            if user2 not in visited:\n                language_cn.update(languages[user2-1])\n                visited.add(user2)\n        \n        # teach the language most of the disconnected users already know, which\n        # is the most common language. The number of people we have to teach then\n        # are disconnected users minus the ones who already speak the most common\n        # language\n        return len(visited) - language_cn.most_common(1)[0][1] if visited else 0\n\n```
['Python3']