需要教语言的最少人数 图解题解

只教一门语言，最少教几个人能让好友都聊上话

有 n 门语言，languages[i] 是第 i 位用户会的语言集合，friendships 列出若干对好友。一对好友能沟通，指两人至少有一门共同语言。你只能挑定一门语言，教给任意几个人，让每一对好友都能沟通，问最少教几个。好友关系没有传递性，x、y 是好友、y、z 是好友，不代表 x、z 是好友。题面第一个例子 n=2、languages=[[1],[2],[1,2]]，答案是 1。

五对好友里，真正卡住的是哪几对

好友只要已有共同语言，就不用碰。真正的麻烦只出在交集为空、也就是两人没有一门语言重合的那种好友对上。把这类说不上话的好友，两端一起收进集合 S。当前就能沟通的人不在 S 里，教他们任何语言都是白教，最少人数只会出在 S 这批人身上。

为什么全教同一门语言、还专挑已会人数最多的

题目卡死只能选一门语言 L，对 S 里的人只能统一教这一门。把 L 教给 S 中还不会 L 的人后，每条问题好友边——即前面收进集合 S 的那些说不上话的好友——的两端就都会 L，这对好友被修好。要教的人数，等于 S 的总人数减去 S 里本来就会 L 的人数——|S| 固定，要让差最小，就得让已会 L 的人数尽量大。于是枚举每门语言，数它在 S 里已有几人会，选已会最多那门，减完剩下就是最少要教的人。

三步写成代码，返回值到底减掉了谁

第一步用 check 判断两个用户有没有共同语言，参考代码里是最直白的双重循环，拿 u 的每门语言去和 v 的每门语言逐个比，相等返回真；遍历每对好友，check 为假就把 u、v 放进 S。第二步用计数器 cnt 走一遍 S 里的人，每人会的语言各记一票。第三步返回 len(S) 减去 cnt 的最高票，即 S 人数减去已会最多那门的人数。S 为空时没有票，返回 0。

n=2 的三人例子，S 和答案怎么落出来

拿题面第一个例子走一遍：用户1 会 {1}，用户2 会 {2}，用户3 会 {1,2}，好友有 (1,2)、(1,3)、(2,3)。(1,2)：{1} 和 {2} 没有重合，两人进 S，S={用户1, 用户2}。(1,3)：{1} 和 {1,2} 共有语言1，能沟通，跳过。(2,3)：{2} 和 {1,2} 共有语言2，跳过。三对看完，S={用户1, 用户2}。

再数 S 里的语言：用户1 会语言1，用户2 会语言2，两门各 1 人会，最高票 1。答案 = |S| 减最高票 = 2 − 1 = 1，教这 1 个人即可：给他补上另一人已会的那门，两人就有了共同语言。

这几处最容易写偏，复杂度也一并算清

想给不同的人教不同语言凑得更省，最招人上当，可题目只准选一门 L，唯有统一教 L，两端才同时会 L。把不在 S 的人也拉进来数，实则稀释每门语言的票数，最优语言和最少人数一起算歪。已会 L 的人天生就能用 L 沟通、不用教，若也算进要教的名单，就成了教满整个 S，正解是减去这批人。复杂度上，设好友对数为 m、单人语言数上限为 k：建 S 时逐对双重循环判交集，是 O(m·k²)；之后只在 S 内统计一遍，是 O(|S|·k)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def minimumTeachings(
        self, n: int, languages: List[List[int]], friendships: List[List[int]]
    ) -> int:
        def check(u: int, v: int) -> bool:
            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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        unordered_set<int> s;
        auto check = [&](int u, int v) {
            for (int x : languages[u - 1]) {
                for (int y : languages[v - 1]) {
                    if (x == y) {
                        return true;
                    }
                }
            }
            return false;
        };
        for (auto& e : friendships) {
            int u = e[0], v = e[1];
            if (!check(u, v)) {
                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());
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Set<Integer> s = new HashSet<>();
        for (int[] 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;
    }
}