并查集与二进制子集

并查集与二进制子集

并查集

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

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);
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:30
点赞 评论 收藏
分享
星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务