题解 | 隐匿社交网络

#include <iostream>
using namespace std;
class set{
    public:
       long long weight;
       int count;
       set(){
           weight = 0;
           count  = 0;
       }
};
int main() {
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        set *s = new set [n];
        int length = 0;//并查集的总数
        for(int i = 0; i < n; ++i){
            long long weight;
            cin>>weight;
            int flag = 0;//并查集中没有
            int first = -1;
            for(int j = 0; j < length; ++j){
                if((weight & s[j].weight) >= 1){
                    if(flag == 0){
                       s[j].weight |= weight;
                       s[j].count++;
                       flag = 1;
                       first = j;
                    }
                    else {
                        s[first].weight |= s[j].weight;
                        s[first].count += s[j].count;
                        s[j].count = 0;
                        s[j].weight = 0;
                    }
                }
            }
            if(flag == 0){
                s[length].weight = weight;
                s[length].count = 1;
                length++;
            }
        }
        // for(int i = 0; i < length; ++i){
        //     cout<<s[i].weight<<" ";
        // }
        // cout<<endl;
        int maxN = 0;
        for(int i = 0; i < length; ++i){
            if(maxN < s[i].count){
                maxN = s[i].count;
            }
        }
        cout<<maxN<<endl;
    }
}
// 64 位输出请用 printf("%lld")