题解 | 隐匿社交网络（并查集+按位遍历）

#牛客春招刷题训练营# + 链接

题意显然是并查集维护size，但是n平方复杂度是不对的

从and考虑按位遍历，稍微注意下细节

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

using ll = long long;
const int MAXN=100010;
ll w[MAXN];

int fa[MAXN], sum[MAXN];

inline int find(int x) {
    if(x != fa[x]) {
        int t = fa[x];
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

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

int main() {
    int T,n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i=1;i<=n;i++) {
            scanf("%lld", w+i);
            fa[i]=i;
            sum[i]=1;
        }
        vector<int> ve;
        for (int k=0;k<=60;k++) {
            for (int i=1;i<=n;i++) if ((w[i]>>k)&1) {
                ve.push_back(i);
            }
            for (int i=1;i<ve.size();i++) {
                merge(ve[0], ve[i]);
            }
            ve.clear();
        }
        printf("%d\n", *max_element(sum+1,sum+n+1));
    }
    return 0;
}