并查集与二进制子集

并查集

思想:用集合中的一个元素代表集合。主要包含查找与合并。（包含路径压缩与按秩合并）

class Djset {
public:
    Djset():count(0){}
    int find(int x){    //查询，进行路径压缩
        if(parent.find(x)==parent.end()){
            parent[x]=x;
            rank[x]=1;
            count++;
        }
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    int getCount(){        //    获取不相交集合的数量
        return count;
    }
    void unionSet(int x,int y){        /*合并不相交的集合，使用按秩合并*/
        int fx=find(x),fy=find(y);
        if(fx==fy){
            return;
        }
        if(rank[fx]<rank[fy]){
            swap(fx,fy);
        }
        rank[fx]+=rank[fy];
        parent[fy]=fx;
        count--;
    }

private:
    unordered_map<int,int> parent,rank;
    int count;
};

通用枚举二进制子集

思想：列举固定长度二进制数的子集。

for(int j=s;j!=s;j=(j-1)&k);