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​​​​​​th​​​​ user knows, and
  • friendships[i] = [u​​​​​​i​​​, v​​​​​​i] denotes a friendship between the users u​​​​​​​​​​​i​​​​​ and vi.

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.

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.

 

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.

 

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​​​​​i, v​​​​​​i) are unique
  • languages[i] contains only unique values

1733. Minimum Number of People to Teach
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);
}