Minimum Number of People to Teach
On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.
You receive an integer n, an array languages, and an array friendships where:
-
There are
nlanguages numbered1throughn, -
languages[i]is the set of languages thei th user knows, and -
friendships[i] = [u i , v i ]denotes a friendship between the usersu i andv i.
You can choose one language and teach it to some users so that all friends can communicate with each other. Produce the minimum number of users you need to teach.
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.
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.
Constraints
2 <= n <= 500languages.length == m1 <= m <= 5001 <= languages[i].length <= n1 <= languages[i][j] <= n1 <= u i < v i <= languages.length1 <= friendships.length <= 500- All tuples
(u i, v i )are unique languages[i]contains only unique values
Did this problem appear in one of your interviews?
Responses stay private.