Subset Component

• Time : O(n 2^n 64 log 64) ≈ O(n * 2^n)
• Space : O(n)

c++

int uf[66];

int find(int u) {
    return u == uf[u] ? u : uf[u] = find(uf[u]);
}

void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu, pv);
}

void reset() {
    for(int i = 0; i < 64; i++) uf[i] = i;
}

int findConnectedComponents(vector<long> d) {
    long long n = d.size();
    int res = 0;
    vector<vector<int>> masks;
    for(auto& a : d) {
        masks.emplace_back();
        for(long long j = 0; j < 64; j++) {
            if(a & (1ll<<j)) masks.back().push_back(j);
        }
    }
    for(long long subset = 0; subset < (1ll<<n); subset++) {
        reset();

        for(long long i = 0; i < n; i++) {
            if(subset & (1ll<<i)) {
                int m = masks[i].size();
                for(long long j = 1; j < m; j++) {
                    uni(masks[i][0], masks[i][j]);
                }
            }
        }

        unordered_set<int> us;
        for(long long i = 0; i < 64; i++)
            us.insert(find(i));
        res += us.size();
    }
    return res;
}