Space: O(m*n), Time: O(m*n)
class Solution(object):\n    def minimumTeachings(self, n, languages, friendships):\n        """\n        :type n: int\n        :type languages: List[List[int]]
class Solution(object):\n    def minimumTeachings(self, n, languages, friendships):\n        """\n        :type n: int\n        :type languages: List[List[int]]\n        :type friendships: List[List[int]]\n        :rtype: int\n        """\n        \n        people = len(languages)+1\n        \n        lang_matrix = [[False for l in range(n+1)] for p in range(people)]\n        \n        non_comm_friends = []\n        for p,l_list in enumerate(languages):\n            for l in l_list:\n                lang_matrix[p+1][l] = True\n        \n        for [u,v] in friendships:\n            comm = False\n            for l in range(1,n+1):\n                if lang_matrix[u][l] and lang_matrix[v][l]:\n                    #print u,v, l\n                    comm = True\n                    break\n            \n            if not comm:\n                non_comm_friends.append([u,v])\n        \n        #print non_comm_friends\n        res = people\n        for l in range(1,n+1):\n            cur = 0\n            people_learned = set()\n            \n            for [u,v] in non_comm_friends:\n                if not lang_matrix[u][l] and u not in people_learned:\n                    cur += 1\n                    people_learned.add(u)\n                    \n                if not lang_matrix[v][l] and v not in people_learned:\n                    cur += 1\n                    people_learned.add(v)\n                \n            res = min(res, cur)\n        \n        return res\n            \n            \n
['Graph']