题目

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

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

总共有 n 种语言，编号从 1 到 n 。
languages[i] 是第 i 位用户掌握的语言集合。
friendships[i] = [ui, vi] 表示 ui 和 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 名用户。

解题思路

核心思想：枚举 + 贪心

这道题的核心问题是“选择一门语言”，这给了我们一个非常重要的提示。总共只有 n 门语言，而 n 的最大值是 500，这是一个相对较小的数字。当问题中有一个选择范围不大（比如几百、几千）的决策点时，我们通常可以考虑枚举所有可能性。

也就是说，我们可以尝试每一种可能性：

如果我们选择语言 1 作为“通用语言”，最少需要教多少人？
如果我们选择语言 2 作为“通用语言”，最少需要教多少人？
…
如果我们选择语言 n 作为“通用语言”，最少需要教多少人？

我们把这 n 种情况的答案都计算出来，然后取其中最小的一个，就是最终的答案。

这样，我们就把一个复杂的问题（“选哪门语言”和“教哪些人”），分解成了 n 个更简单、更具体的问题：

“如果我们已经确定了要推广的语言是 L，那么最少需要教多少人？”

解决子问题：固定一门语言 L，计算成本

现在我们来解决这个子问题。假设我们已经选定了语言 L 作为我们的“通用语言”。我们的目标是让所有好友之间都能沟通。

我们需要遍历每一对好友关系 [u, v]，并检查他们的情况：

检查好友 u 和 v 是否已经可以沟通？
- “可以沟通”的条件是他们掌握的语言集合有交集。
- 我们可以检查 languages[u-1] 和 languages[v-1] 这两个集合是否有共同的元素。（注意：题目给的用户编号是 1-based，数组索引是 0-based，需要-1处理）。
- 如果他们已经可以沟通了，那么这对好友关系已经“满足”了，我们不需要为他们做任何事。
如果好友 u 和 v 不能沟通，我们该怎么办？
- 如果他们的语言集合没有交集，那么这对好友关系就是“未满足”的。
- 为了让他们能沟通，我们必须利用我们选定的“通用语言” L。
- 要让他们通过语言 L 沟通，就意味着用户 u 和用户 v 都必须会说语言 L。
- 所以，我们需要检查：
  - 用户 u 会不会说语言 L？如果不会，我们就必须教他。
  - 用户 v 会不会说语言 L？如果不会，我们就必须教他。
如何统计总人数？
- 在遍历所有好友关系时，我们会遇到很多需要教语言 L 的用户。
- 同一个用户可能会因为不同的好友关系而被多次判定为“需要教”。例如，用户A和B不通，用户A和C也不通，那么在处理 [A, B] 和 [A, C] 时，我们都会判定“需要教A”。
- 为了避免重复计算，我们可以使用一个集合（Set）来存储所有需要教语言 L 的用户。每次判定一个用户需要被教时，就把他的ID加入这个集合。
- 遍历完所有好友关系后，这个集合的大小，就是选择语言 L 时需要教的总人数。

综合起来，完整的解题步骤如下：

初始化一个变量 min_cost 为一个最大值（例如，用户总数 m），用来记录所有情况下的最小教学人数。
数据预处理（可选但推荐）：为了后续快速查询，最好先把 languages 数组中的每个用户的语言列表转换成哈希集合（Set）。这样检查一个用户是否会某门语言，以及求两个用户语言的交集都会更高效。
主循环（枚举语言）：写一个循环，从 l = 1 到 n，遍历每一门可以作为“通用语言”的语言 l。
内层逻辑（计算当前语言的成本）：
- a. 在循环内部，创建一个空的哈希集合 users_to_teach，用于存放当前语言 l 需要教的用户。
- b. 遍历 friendships 数组中的每一对好友 [u, v]。
- c. 检查沟通状态：判断用户 u和 v 的语言集合是否有交集。
- d. 处理无法沟通的好友：如果他们没有交集（即无法沟通）：
  - i. 检查用户 u的语言集合中是否包含语言 l。如果不包含，则将 u 加入 users_to_teach 集合。
  - ii. 检查用户 v 的语言集合中是否包含语言 l。如果不包含，则将 v 加入 users_to_teach 集合。
- e. 当遍历完所有好友关系后，users_to_teach 集合的大小就是推广语言 l 所需要教的人数，我们称之为 current_cost。
更新最小成本：比较 current_cost 和 min_cost，将 min_cost 更新为两者中较小的一个：min_cost = min(min_cost, current_cost)。
返回结果：主循环结束后，min_cost 中存储的就是最终的答案，返回它即可。

复杂度分析

设 n 为语言数量，m 为用户数量，f 为好友关系数量，k 为单个用户掌握语言的最大数量。
时间复杂度:
- 外层循环 n 次（遍历所有语言）。
- 内层循环 f 次（遍历所有好友关系）。
- 在内层循环中，检查两个用户语言是否有交集。如果预处理成了集合，平均耗时 O(k)。检查用户是否会某门语言，平均耗时 O(1)。
- 因此，总的时间复杂度大约是 O(n * f * k)。根据题目给定的数据范围 (500 * 500 * 500)，这个解法可能会比较慢，但通常在这种约束下是可以通过的。如果语言列表没有转成集合，每次查找和求交集都是 O(k)，那么复杂度也是类似的。
空间复杂度:
- 如果我们将所有用户的语言列表转为集合，需要 O(m * k) 的空间。
- 在每次内层循环中，需要一个集合来存储待教用户，最多 O(m) 的空间。
- 所以总空间复杂度为 O(m * k)。

具体代码

class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        
        // 获取用户总数 m
        int m = languages.size();

        // --- 数据预处理 ---
        // 为了后续能以 O(1) 的平均时间复杂度快速查询某个用户是否会某门语言，
        // 我们将每个用户的语言列表 (vector) 转换为哈希集合 (unordered_set)。
        vector<unordered_set<int>> lang_sets(m);
        for (int i = 0; i < m; ++i) {
            // languages[i] 是第 i+1 个用户的语言列表
            for (int lang : languages[i]) {
                lang_sets[i].insert(lang);
            }
        }

        // --- 找出所有无法直接沟通的好友对 ---
        // 我们的目标只是为了让这些无法沟通的人能够沟通，
        // 已经可以沟通的好友对不需要我们做任何额外操作。
        // 因此，先筛选出这些“问题”好友对，可以减少后续的重复计算。
        vector<pair<int, int>> non_communicating_friends;
        for (const auto& friendship : friendships) {
            // 用户编号是 1-based，需要-1转换为 0-based 数组索引
            int u = friendship[0] - 1;
            int v = friendship[1] - 1;

            // 检查 u 和 v 是否有共同语言
            bool can_communicate = false;
            // 优化：遍历较小的集合，在较大的集合中查找，效率更高
            const auto& smaller_set = lang_sets[u].size() < lang_sets[v].size() ? lang_sets[u] : lang_sets[v];
            const auto& larger_set = lang_sets[u].size() < lang_sets[v].size() ? lang_sets[v] : lang_sets[u];

            for (int lang : smaller_set) {
                if (larger_set.count(lang)) { // count 在哈希集合中是 O(1) 操作
                    can_communicate = true;
                    break; // 找到一门共同语言就足够了
                }
            }
            
            // 如果不能沟通，将这对好友（用1-based编号）记录下来
            if (!can_communicate) {
                non_communicating_friends.push_back({u + 1, v + 1});
            }
        }

        // 如果所有好友都能沟通，不需要教任何人
        if (non_communicating_friends.empty()) {
            return 0;
        }

        // --- 枚举每种语言作为通用语言 ---
        // 初始化一个最小教学人数，初始值可以设为用户总数 m，这是一个安全的最大值。
        int min_teachings = m;

        // 遍历每一种语言 l (从 1 到 n)，尝试将其作为通用语言
        for (int l = 1; l <= n; ++l) {
            
            // 使用哈希集合来存储在当前语言 l 的情况下，需要被教的用户。
            // 使用集合可以自动处理重复问题。
            unordered_set<int> users_to_teach;
            
            // 只需要遍历那些无法沟通的好友对
            for (const auto& p : non_communicating_friends) {
                int u = p.first;  // 用户编号 u (1-based)
                int v = p.second; // 用户编号 v (1-based)

                // 检查用户 u 是否会语言 l，如果不会，则需要教他
                // lang_sets 的索引是 0-based，所以用 u-1
                if (lang_sets[u - 1].count(l) == 0) {
                    users_to_teach.insert(u);
                }

                // 检查用户 v 是否会语言 l，如果不会，则需要教他
                if (lang_sets[v - 1].count(l) == 0) {
                    users_to_teach.insert(v);
                }
            }
            
            // 更新全局的最小教学人数
            min_teachings = min(min_teachings, (int)users_to_teach.size());
        }

        return min_teachings;
    }
};

优化思路

之前的方法是“枚举语言”，时间复杂度大概是 O(n * f * k) 或 O(n * f')（其中 f' 是无法沟通的好友对数量）。当 n 和 f 都很大时，这个乘积项是主要的性能瓶颈。

更优的方法可以转换思考角度，从“枚举语言”变为“分析用户”，从而优化掉一个循环。

核心思想：找到在“问题人群”中最普及的语言

“问题人群”是谁？
- 首先，如果一对好友 [u, v] 已经可以沟通了，那他们就不在我们的考虑范围之内。我们不需要为他们做任何事。
- 我们真正需要关注的，是那些当前无法沟通的好友对。所有参与到这些“无法沟通”关系里的用户，构成了我们的“问题人群”（problem users）。只有这些人才有可能需要被教新语言。
我们的目标是什么？
- 我们的目标是在这个“问题人群”中推广一门语言 L，使得所有无法沟通的关系都被修复。
- 修复关系 [u, v] 的方法是让 u 和 v 都会说 L。
- 需要付出的成本（教学人数） = “问题人群"的总人数 - 在这个人群中已经会说 L 的人数。
- 为了让成本最小化，我们就需要让“在问题人群中已经会说 L 的人数”最大化。
新的解法
- 这就把问题转化为了：在所有“问题人群”中，哪一门语言是他们会的最多、最普及的？
- 我们只要找到这门最普及的语言，把它定为我们的通用语言，就可以最大化地利用他们已有的知识，从而最小化需要教学的人数。

优化后算法步骤

找出所有“问题”用户 (Problem Users)
- 创建一个哈希集合 problem_users，用来存放所有涉及无法沟通关系的用户ID。
- 遍历 friendships 数组中的每一对好友 [u, v]。
- 检查 u 和 v 是否可以沟通（方法同前，检查语言集合有无交集）。
- 如果不能沟通，就把 u 和 v 的用户ID都加入到 problem_users 集合中。
统计“问题”用户中各语言的普及度
- 创建一个频率数组（或哈希表） lang_counts，大小为 n+1，初始化为0。lang_counts[l] 用来记录语言 l 在 problem_users 中出现了多少次。
- 遍历 problem_users 集合中的每一个用户 p。
- 对于用户 p，遍历他所会的所有语言 lang。
- 每遍历到一个语言 lang，就给对应的计数器加一：lang_counts[lang]++。
计算最终结果
- 遍历完所有问题用户后，lang_counts 数组就记录了每门语言在问题人群中的普及程度。
- 找到 lang_counts 数组中的最大值，我们称之为 max_coverage。这个值代表了如果我们选择最优的语言，最多可以覆盖多少个“问题用户”（即这些人不需要再教了）。
- “问题人群”的总人数是 problem_users.size()。
- 最终结果（最少需要教的人数） = problem_users.size() - max_coverage。
- 特殊情况：如果 problem_users 为空（即所有好友都能沟通），那么它的 size() 是0，max_coverage 也是0，结果为0，符合预期。

复杂度分析对比

原方法
- 时间复杂度: O(m*k + n*f*k) 或 O(m*k + n*f')。主要瓶颈在于 n 和 f 的双重循环。
- 大致可以看作 O(n * f)。
优化后方法
- 1. 找出问题用户：遍历所有好友关系，每次检查耗时 O(k)。总共 O(f * k)。
- 1. 统计语言频率：遍历所有问题用户（最多 m 个），再遍历他们的语言（最多 k 个）。总共 O(m * k)。
- 1. 找最大值：遍历频率数组，耗时 O(n)。
- 总时间复杂度: O(f*k + m*k + n)。
- 大致可以看作 O((f+m)*k + n)。

优化后代码

class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        
        // --- 步骤 0: 数据预处理 ---
        // 将 vector 转换为 unordered_set 以便快速查询
        int m = languages.size();
        vector<unordered_set<int>> lang_sets(m);
        for (int i = 0; i < m; ++i) {
            lang_sets[i].insert(languages[i].begin(), languages[i].end());
        }

        // --- 步骤 1: 找出所有“问题”用户 ---
        // 创建一个哈希集合，用于存储所有参与了“无法沟通”关系的用户ID
        unordered_set<int> problem_users;
        for (const auto& friendship : friendships) {
            // 用户编号是 1-based, 数组索引是 0-based
            int u_idx = friendship[0] - 1;
            int v_idx = friendship[1] - 1;

            // 检查 u 和 v 是否有共同语言
            bool can_communicate = false;
            const auto& u_langs = lang_sets[u_idx];
            const auto& v_langs = lang_sets[v_idx];

            // 优化：总是遍历较小的集合
            const auto& smaller_set = u_langs.size() < v_langs.size() ? u_langs : v_langs;
            const auto& larger_set = u_langs.size() < v_langs.size() ? v_langs : u_langs;

            for (const int& lang : smaller_set) {
                if (larger_set.count(lang)) {
                    can_communicate = true;
                    break;
                }
            }
            
            // 如果不能沟通, 将这对好友的ID(1-based)加入问题集合
            if (!can_communicate) {
                problem_users.insert(friendship[0]);
                problem_users.insert(friendship[1]);
            }
        }

        // 如果没有问题用户，说明所有好友都能沟通，成本为0
        if (problem_users.empty()) {
            return 0;
        }

        // --- 步骤 2: 统计“问题”用户中各语言的普及度 ---
        // 创建一个频率数组，lang_counts[l] 表示语言 l 在问题用户中出现的次数
        vector<int> lang_counts(n + 1, 0);
        for (const int& user_id : problem_users) {
            // lang_sets 的索引是 0-based
            for (const int& lang : lang_sets[user_id - 1]) {
                lang_counts[lang]++;
            }
        }

        // --- 步骤 3: 计算最终结果 ---
        // 找到问题用户中最普及的语言覆盖了多少人
        int max_coverage = 0;
        for (int i = 1; i <= n; ++i) {
            if (lang_counts[i] > max_coverage) {
                max_coverage = lang_counts[i];
            }
        }
        
        // 最少需要教的人数 = 问题用户的总数 - 最优语言能覆盖的人数
        return problem_users.size() - max_coverage;
    }
};

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

题目