题解 | 隐匿社交网络

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

int find(vector<int> &p, int x) {
    if (p[x] < 0) return x;
    else return p[x] = find(p, p[x]);
}

void unio(vector<int> &p, int x, int y) {
    int rootx = find(p, x);
    int rooty = find(p, y);
    if (rootx == rooty) return;
    if (abs(p[rootx]) >= abs(p[rooty])) {
        p[rootx] += p[rooty];
        p[rooty] = rootx;
    } else {
        p[rooty] += p[rootx];
        p[rootx] = rooty;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, ma = 1;
        cin >> n;
        vector<bitset<64>> bbb;
        for (int i = 0; i < n; i++) {
            long long x;
            cin >> x;
            bitset<64> xx(x);
            bbb.push_back(xx);
        }

        int total_nodes = n + 64;
        vector<int> p(total_nodes, -1);

        // 处理合并
        for (int i = 0; i < n; i++) {
            for (int bit = 0; bit < 64; bit++) {
                if (bbb[i][bit]) {
                    int virtual_node = n + bit;
                    unio(p, i, virtual_node);
                }
            }
        }

        // 统计每个集合中真实账号的数量
        vector<int> cnt(total_nodes, 0);
        for (int i = 0; i < n; i++) { // 只遍历真实账号
            int root = find(p, i);
            cnt[root]++; // 每个真实账号对应集合的cnt+1
        }

        // 找最大的真实账号数量
        for (int i = 0; i < n; i++) {
            int root = find(p, i);
            ma = max(ma, cnt[root]);
        }

        cout << ma << endl;
    }
    return 0;
}