Question

1733. 需要教语言的最少人数

English Version

题目描述

在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。

给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：

• 总共有 n 种语言，编号从 1 到 n 。
• languages[i] 是第 i 位用户掌握的语言集合。
• friendships[i] = [u​​​​​​i​​​, v​​​​​​i] 表示 u​​​​​​​​​​​i​​​​​ 和 vi 为好友关系。

你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。

请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。

 

示例 1：

输入：n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
输出：1
解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。

示例 2：

输入：n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
输出：2
解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。

 

提示：

• 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
• 所有的好友关系 (u​​​​​i, v​​​​​​i) 都是唯一的。
• languages[i] 中包含的值互不相同。

解法

方法一：模拟 + 统计

对于每个好友关系，如果两个人掌握的语言集合不相交，则需要教一门语言，使得两个人可以相互沟通，我们将这些人放入一个哈希集合 $s$ 中。

然后在这个集合 $s$ 中，统计每种语言掌握的人数，获取最大的人数，我们记为 $mx$，那么答案就是 len(s) - mx。

时间复杂度 $O(m^2\times k)$。其中 $m$ 为语言的数量，而 $k$ 为好友关系的数量。

class Solution:
  def minimumTeachings(
    self, n: int, languages: List[List[int]], friendships: List[List[int]]
  ) -> int:
    def check(u, v):
      for x in languages[u - 1]:
        for y in languages[v - 1]:
          if x == y:
            return True
      return False

    s = set()
    for u, v in friendships:
      if not check(u, v):
        s.add(u)
        s.add(v)
    cnt = Counter()
    for u in s:
      for l in languages[u - 1]:
        cnt[l] += 1
    return len(s) - max(cnt.values(), default=0)

class Solution {
  public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
    Set<Integer> s = new HashSet<>();
    for (var e : friendships) {
      int u = e[0], v = e[1];
      if (!check(u, v, languages)) {
        s.add(u);
        s.add(v);
      }
    }
    if (s.isEmpty()) {
      return 0;
    }
    int[] cnt = new int[n + 1];
    for (int u : s) {
      for (int l : languages[u - 1]) {
        ++cnt[l];
      }
    }
    int mx = 0;
    for (int v : cnt) {
      mx = Math.max(mx, v);
    }
    return s.size() - mx;
  }

  private boolean check(int u, int v, int[][] languages) {
    for (int x : languages[u - 1]) {
      for (int y : languages[v - 1]) {
        if (x == y) {
          return true;
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
    unordered_set<int> s;
    for (auto& e : friendships) {
      int u = e[0], v = e[1];
      if (!check(u, v, languages)) {
        s.insert(u);
        s.insert(v);
      }
    }
    if (s.empty()) {
      return 0;
    }
    vector<int> cnt(n + 1);
    for (int u : s) {
      for (int& l : languages[u - 1]) {
        ++cnt[l];
      }
    }
    return s.size() - *max_element(cnt.begin(), cnt.end());
  }

  bool check(int u, int v, vector<vector<int>>& languages) {
    for (int x : languages[u - 1]) {
      for (int y : languages[v - 1]) {
        if (x == y) {
          return true;
        }
      }
    }
    return false;
  }
};

func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
  check := func(u, v int) bool {
    for _, x := range languages[u-1] {
      for _, y := range languages[v-1] {
        if x == y {
          return true
        }
      }
    }
    return false
  }
  s := map[int]bool{}
  for _, e := range friendships {
    u, v := e[0], e[1]
    if !check(u, v) {
      s[u], s[v] = true, true
    }
  }
  if len(s) == 0 {
    return 0
  }
  cnt := make([]int, n+1)
  for u := range s {
    for _, l := range languages[u-1] {
      cnt[l]++
    }
  }
  return len(s) - slices.Max(cnt)
}