题解 | 隐匿社交网络

#include <any>
#include <iostream>
#include <vector>
using namespace std;

class Total_set {
  public:
    vector<int> parent; // 父节点数组
    vector<int> cnt;     // 每个集合的账号数量

  
    Total_set(const int size) {
        parent.resize(size);
        cnt.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // 初始父节点为自己
        }
    }

    int find(const int& x) {
        if (parent[x] != x) {
            return find(parent[x]);
        }
        return x;
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        // 总将小根作为父节点，保证合并方向一致
        if (x > y) {
            swap(x, y);
        }
        parent[y] = x;
        cnt[x] += cnt[y];
    }

};

void solve() {
    int n;
    cin >> n;
    Total_set uf(61); // 0-60位

    for (int i = 0; i < n; ++i) {
        long long w;
        cin >> w;
        vector<int> bits;
        // 分解数字为二进制位：获取所有为1的位
        while (w) {
            int b = __builtin_ctzll(w); // 获取最低位的1的位置
            bits.push_back(b);
            w ^= (1LL << b); // 清除已处理的位
        }
        if (bits.empty()) continue; // w=0的情况（题目保证w≥1，可省略）

        // 合并所有位到第一个位的集合
        int root = uf.find(bits[0]);
        for (int j = 1; j < bits.size(); ++j) {
            uf.unite(root, bits[j]);
        }
        // 将当前账号计数加到合并后的根节点
        root = uf.find(root);
        uf.cnt[root]++;
    }

    // 遍历所有位，找到最大集合
    int max_count = 0;
    for (int b = 0; b <= 60; ++b) {
        if (uf.find(b) == b) { // 只检查根节点
            max_count = max(max_count, uf.cnt[b]);
        }
    }
    cout << max_count << '\n';
}


int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
// 64 位输出请用 printf("%lld")