1733. Minimum Number of People to Teach Medium

1/**
2 * [1733] Minimum Number of People to Teach
3 *
4 * 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.
5 * You are given an integer n, an array languages, and an array friendships where:
6 * 
7 * 	There are n languages numbered 1 through n,
8 * 	languages[i] is the set of languages the i^​​​​​​th​​​​ user knows, and
9 * 	friendships[i] = [u​​​​​​i​​​, v​​​​​​i] denotes a friendship between the users u^​​​​​​​​​​​i​​​​​ and vi.
10 * 
11 * You can choose one language and teach it to some users so that all friends can communicate with each other. Return <i data-stringify-type="italic">the minimum <i data-stringify-type="italic">number of users you need to teach.
12 * Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.
13 *  
14 * Example 1:
15 * 
16 * Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
17 * Output: 1
18 * Explanation: You can either teach user 1 the second language or user 2 the first language.
19 * 
20 * Example 2:
21 * 
22 * Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
23 * Output: 2
24 * Explanation: Teach the third language to users 1 and 3, yielding two users to teach.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	2 <= n <= 500
30 * 	languages.length == m
31 * 	1 <= m <= 500
32 * 	1 <= languages[i].length <= n
33 * 	1 <= languages[i][j] <= n
34 * 	1 <= u​​​​​​i < v​​​​​​i <= languages.length
35 * 	1 <= friendships.length <= 500
36 * 	All tuples (u​​​​​i, v​​​​​​i) are unique
37 * 	languages[i] contains only unique values
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/minimum-number-of-people-to-teach/
43// discuss: https://leetcode.com/problems/minimum-number-of-people-to-teach/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_1733() {
61    }
62}
63