题解 | 隐匿社交网络

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define fo(i,a,b) for(int i=a;i<b;i++) // 定义一个循环宏，用于简化循环代码

vector<ll>a(64); // 并查集的父数组，用于记录每个位的父节点

// 并查集的查找函数，带路径压缩
int find(int x){
    if(a[x]!=x){ // 如果当前节点不是根节点
        a[x]=find(a[x]); // 递归查找根节点，并进行路径压缩
    }
    return a[x]; // 返回根节点
}

// 并查集的合并函数
void arrage_sum(int x,int y){
    x=find(x); // 找到x的根节点
    y=find(y); // 找到y的根节点
    if(x!=y){ // 如果x和y不在同一个集合
        a[x]=a[y]; // 将x的根节点指向y的根节点，合并两个集合
    }
}

int main() {
    ll n; // 测试用例的数量
    cin>>n;
    while(n--){ // 对每个测试用例进行处理
        ll m; // 当前测试用例的权重数量
        cin>>m;
        vector<vector<int>>vv(64); // 用于记录每个位上为1的权重的下标
        vector<ll>v(m); // 存储当前测试用例的所有权重
        fo(i,0,64)a[i]=i; // 初始化并查集，每个位是一个独立的集合
        fo(i,0,m){ // 遍历每个权重
            cin>>v[i]; // 读取权重
            vector<ll>b; // 用于记录当前权重的二进制表示中为1的位
            for(int j=0;j<64;j++){ // 遍历每个位
                if((v[i]>>j)&1){ // 如果当前位是1
                    vv[j].emplace_back(i); // 记录该权重的下标
                    b.emplace_back(j); // 记录该位
                }
            }
            if(b.size()>1){ // 如果当前权重有多个1位
                fo(k,1,b.size()){ // 遍历这些1位
                    arrage_sum(b[k-1],b[k]); // 将这些位对应的集合合并
                }
            }
        }
        fo(i,0,64){ // 遍历每个位
            int x=find(i); // 找到该位的根节点
            if(x!=i){ // 如果该位不是根节点
                fo(j,0,vv[i].size()){ // 将该位的所有权重下标合并到根节点对应的集合
                    vv[x].emplace_back(vv[i][j]);
                }
                sort(vv[x].begin(),vv[x].end()); // 对合并后的集合进行排序
            }
        }
        int ans=0; // 用于记录最大的社交网络大小
        fo(i,0,64){ // 遍历每个集合
            ll flag=0; // 用于记录重复的权重下标
            if(vv[i].size()>1){ // 如果集合大小大于1
                fo(j,1,vv[i].size()){ // 遍历集合
                    if(vv[i][j]==vv[i][j-1]){ // 如果有重复的权重下标
                        flag++; // 增加重复计数
                    }
                }
            }
            ans=max(ans,int(vv[i].size()-flag)); // 更新最大的社交网络大小
        }
        cout<<ans<<'\n'; // 输出结果
    }
    return 0;
}