题解 | 隐匿社交网络

#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int N = 100010;
int w[N],s[N];
int fa[N];
int find(int x){
    if(x!=fa[x]){
        int t = fa[x];
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

void merge(int x,int y){
    x = find(x);
    y = find(y);
    if(x!=y){
        fa[x] = y;
        s[y]+=s[x];
    }
}
void solve(){

    int n;cin>>n;
    int res = 1;
    for(int i = 1;i<=n;i++){
        cin>>w[i];
        fa[i] = i;
        s[i] = 1;
    }
    vector<int>pre;
    for(int k = 0;k<=60;k++){
        for(int i = 1;i<=n;i++){
            if((w[i]>>k)&1){
                pre.push_back(i);
            }
        }
        for(int i = 0;i<pre.size();i++){
            merge(pre[0], pre[i]);
        }
        pre.clear();
    }
    for(int i = 1;i<=n;i++){
        res = max(res,s[i]);
    }
    
    cout<<res<<'\n';

}
signed main() {

    int t = 1;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

看了大佬的解法

1. 我们需要将账号分成多个社交网络，其中两个账号属于同一网络当且仅当它们的权重按位与结果至少为1这实际上意味着两个账号至少有一个相同的二进制位为1直接统计每个二进制位的出现次数并不能完全反映社交网络的结构，因为账号可能通过多个不同的二进制位间接连接
2. 账号之间的连接关系具有传递性：如果账号A和B有共同位，B和C有共同位，那么A、B、C属于同一网络因此需要使用并查集来维护连通分量
3. 使用并查集来维护账号的连通性对于每个二进制位，将该位上为1的所有账号合并最后统计最大的连通分量大小。

活动地址https://www.nowcoder.com/discuss/726480854079250432