C++刷LeetCode（1733. 需要教语言的最少人数***）【数学】

糖逗

题目描述：

在一个由 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] 中包含的值互不相同。

class Solution {
public:
    //判断两个人之间是否有共同语言
    bool solution(vector<vector<int> >&language, int i, int j){
        vector<int>temp1 = language[i-1];
        vector<int>temp2 = language[j-1];
        for(auto cha1 : temp1){
            for(auto cha2 : temp2){
                if(cha1 == cha2)return true;
            }
        }
        return false;
    }
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        map<int, int>store1;
        map<int, int>store2;
        //记录每个人在自己的好友名单中，没有共同语言的好友人数
        for(int i = 0; i < friendships.size(); i++){
            if(!solution(languages, friendships[i][0], friendships[i][1])){
                store1[friendships[i][0]]++;
                store1[friendships[i][1]]++;
            }
        }
        //统计store1中所有人会的语言和语言数
        for (auto p: store1) {
            for (auto language: languages[p.first-1]) {
                store2[language]++;
            }
        }
        //找到最通用的语言
        int store = 0;
        for(auto cha : store2){
            store = max(store, cha.second);
        }

        return store1.size() - store;
    }
};

参考链接：https://leetcode-cn.com/problems ... ong-tong-yu-y-eptr/

糖逗

几级石阶

这是啥大神，占个沙发观望。