You are viewing a single comment's thread. Return to all comments →
C++ Solution using bitmask and bitwise OR.
int findConnectedComponents(vector<long> d) { int n = d.size(); long long ans = 0; for(int i=0;i<(1<<n);++i){ vector<long long> v; vector<vector<int> > a(64); for(long long j=0;j<n;++j){ long long bb = pow(2, j); if((1<<j)&i){ v.push_back(d[j]); } } int par[64]; for(int j=0;j<64;++j)par[j]=0; int cnt = 0; set<long long> vv; for(int j=0;j<v.size();++j){ while(1){ int flag = 0; for(auto xx: vv){ if(xx&v[j]){ v[j]=(v[j]|xx); vv.erase(xx); flag=1; break; } } if(flag) continue; if(flag==0)break; } vv.insert(v[j]); } cnt = 0; int pp = 1; for(auto xx: vv){ for(int j=0;j<64;++j){ long long dd = pow(2, j); if(xx&dd){par[j]=pp; cnt = max(cnt,pp);} } pp++; } for(int j=0;j<64;++j)if(par[j]==0)par[j]=pp++, cnt = max(cnt, par[j]); vv.clear(); ans = ans + cnt; v.clear(); a.clear(); } return ans; }
Subset Component
You are viewing a single comment's thread. Return to all comments →
C++ Solution using bitmask and bitwise OR.