#1733

Minimum Number of People to Teach

specialist · 655 · lc medium +30 · verified · 67.7% accepted · 716 likes · top 74%

Description

On a social network with m users, two users can communicate only if they share a language. Given n languages, languages[i] (user i's languages), and friendships[i] = [ui, vi], you may teach one language to any users so all friends can communicate. Return the minimum number of users to teach.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]

Output: 1

Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]

Output: 2

Explanation: Teach the third language to users 1 and 3, yielding two users to teach.

Code

1

2

3

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int: