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

解题思路

因为语言的数目n最大只有500，所以我们可以用8个64位整数来表示某个用户会的语言数。由于需要判断两个用户是否都会相同的语言，常规的Bitset类不支持该判断，所以我们可以自己实现一个BitSet类。该类支持将某个用户会的语言设置到8个64位整数中，同时支持用户是否会某种语言。

有了BitSet类之后，我们可以直接通过and运算来判断两个用户是否都会某种语言。进而我们可以直接遍历所有的语言，然后判断哪种语言需要教的人最少。这里需要注意两点：

1. 如果两个好友之间已经有都会的语言，后续可以将该条边删除；
2. 指定当前要判断的语言之后，要判断某个用户是否已经被处理过；

代码实现

//神奇的加速代码，与主逻辑无关
int __FAST_IO__ = []() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    return 0;
}();

class BitSet {
public:
    uint64_t bits[8];

    BitSet(vector<int>& language) {
        memset(bits,0, 64);
        for(auto l:language) {
            int high=l>>6;
            int low=l&0x3f;
            bits[high]|=(1ull<<low);
        }
    }

    bool hasBit(int idx) {
        int high=idx>>6;
        int low=idx&0x3f;
        return (bits[high]&(1ull<<low))!=0;
    }
};

class Solution {
public:
    bool hasSameBit(BitSet* first, BitSet* second) {
        for(int i=0;i<8;i++) {
            if((first->bits[i]&second->bits[i])!=0) {
                return true;
            }
        }

        return false;
    }

    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int ans=INT_MAX;
        int m=languages.size();
        vector<BitSet*> sl(m+1);
        for(int i=0;i<m;i++) {
            sl[i+1]=new BitSet(languages[i]);
        }

        vector<vector<int>> droppedFriendShips;
        for(auto& f:friendships) {
            if(!hasSameBit(sl[f[0]],sl[f[1]])) {
                droppedFriendShips.push_back(f);
            }
        }

        for(int i=1;i<=n;i++) {
            int cur=0;
            vector<bool> visited(m+1);

            for(auto& f:droppedFriendShips) {
                if(!visited[f[0]]&&!sl[f[0]]->hasBit(i)) {
                    visited[f[0]]=true;
                    cur++;
                }
                if(!visited[f[1]]&&!sl[f[1]]->hasBit(i)) {
                    visited[f[1]]=true;
                    cur++;
                }
            }

            ans=min(ans,cur);
        }

        return ans;
    }
};

运行截图

时空分析

• 时间复杂度：假设m和n相等，用户好友关系数也为n。第一个for循环构造每个用户会的语言BitSet，复杂度为O(n^2)，第二个循环去除有共同语言的好友关系，复杂度O(n)，第三个循环遍历所有的语言统计最小值，复杂度也为O(n^2)，所以总的复杂度为O(n^2)；
• 空间复杂度：额外的空间耗费在BitSet和简化之后的friendShip关系，空间均为O(n)。