题解 | 隐匿社交网络

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;  // 读取当前测试用例的账号数量
    vector<long long> a(n);  // 存储每个账号的权重
    for (int i = 0; i < n; i++)
        cin >> a[i];  // 读取每个账号的权重

    // 使用map记录连通块：
    // key: 连通块的特征值（该连通块所有账号权重的按位或）
    // value: 该连通块包含的账号数量
    map<long long, int> m;

    int ans = 0;  // 记录最大连通块的大小

    // 遍历每个账号
    for (int i = 0; i < n; i++) {
        vector<long long>
        ks;  // 存储需要与当前账号合并的连通块的特征值

        // 遍历已有连通块，检查哪些与当前账号连通
        for (auto [k, v] : m) {
            // 如果当前账号权重a[i]与连通块特征值k的按位与结果>=1
            // 说明它们有共同位，应该合并到同一连通块
            if ((a[i] & k) >= 1) {
                ks.push_back(k);  // 记录需要合并的连通块
            }
        }

        long long kk = a[i];  // 新连通块的特征值，初始为当前账号权重
        int cnt = 0;  // 统计需要合并的连通块的总账号数

        // 合并所有需要合并的连通块
        for (long long k : ks) {
            kk |= k;     // 更新新连通块特征值（按位或合并）
            cnt += m[k]; // 累加被合并连通块的账号数
            m.erase(k);  // 从map中移除被合并的连通块
        }

        // 创建新连通块（包含当前账号）：
        // 新连通块大小 = 被合并连通块的账号总数 + 当前账号
        m[kk] = cnt + 1;

        // 更新最大连通块大小
        ans = max(ans, cnt + 1);
    }

    // 输出当前测试用例的最大连通块大小
    cout << ans << "\n";
}

int main() {
    int n;
    cin >> n;  // 读取测试用例数量
    while (n--) {
        solve();  // 处理每个测试用例
    }
}