## 1733. 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 are given an integer `n`

, an array `languages`

, and an array `friendships`

where:

- There are
`n`

languages numbered`1`

through`n`

, `languages[i]`

is the set of languages the`i`

user knows, and^{th}`friendships[i] = [u`

denotes a friendship between the users_{i}, v_{i}]`u`

and^{}_{i}`v`

._{i}

You can choose **one** language and teach it to some users so that all friends can communicate with each other. Return *the* **minimum** *number of users you need to teach.*

`x`

is a friend of `y`

and `y`

is a friend of `z`

, this doesn't guarantee that `x`

is a friend of `z`

.

**Example 1:**

Input:n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]Output:1Explanation: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:2Explanation:Teach the third language to users 1 and 3, yielding two users to teach.

**Constraints:**

`2 <= n <= 500`

`languages.length == m`

`1 <= m <= 500`

`1 <= languages[i].length <= n`

`1 <= languages[i][j] <= n`

`1 <= u`

_{i}< v_{i}<= languages.length`1 <= friendships.length <= 500`

- All tuples
`(u`

are unique_{i, }v_{i}) `languages[i]`

contains only unique values

## Rust Solution

```
struct Solution;
use std::collections::HashSet;
impl Solution {
fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
let m = languages.len();
let mut people: Vec<HashSet<i32>> = vec![HashSet::new(); m];
for i in 0..m {
for &j in languages[i].iter() {
people[i].insert(j);
}
}
let friendships: Vec<Vec<i32>> = friendships
.into_iter()
.filter(|rel| {
let u = rel[0] as usize - 1;
let v = rel[1] as usize - 1;
people[u].is_disjoint(&people[v])
})
.collect();
let mut res = m;
let mut disjoints = vec![vec![false; m]; m];
for pair in friendships.iter() {
let u = pair[0] as usize - 1;
let v = pair[1] as usize - 1;
if people[u].is_disjoint(&people[v]) {
disjoints[u][v] = true;
}
}
for i in 1..=n {
let mut teach = HashSet::new();
for pair in friendships.iter() {
let u = pair[0] as usize - 1;
let v = pair[1] as usize - 1;
if disjoints[u][v] {
if !people[u].contains(&i) {
teach.insert(u);
}
if !people[v].contains(&i) {
teach.insert(v);
}
}
}
res = res.min(teach.len());
}
res as i32
}
}
#[test]
fn test() {
let n = 2;
let languages = vec_vec_i32![[1], [2], [1, 2]];
let friendships = vec_vec_i32![[1, 2], [1, 3], [2, 3]];
let res = 1;
assert_eq!(Solution::minimum_teachings(n, languages, friendships), res);
let n = 3;
let languages = vec_vec_i32![[2], [1, 3], [1, 2], [3]];
let friendships = vec_vec_i32![[1, 4], [1, 2], [3, 4], [2, 3]];
let res = 2;
assert_eq!(Solution::minimum_teachings(n, languages, friendships), res);
}
```

Having problems with this solution? Click here to submit an issue on github.