彩世界平台-彩世界时时app-彩世界开奖app苹果下载

热门关键词: 彩世界平台,彩世界时时app,彩世界开奖app苹果下载

您的位置:彩世界平台 > 彩世界平台 > hdu1829 A Bug's Life(并查集)

hdu1829 A Bug's Life(并查集)

发布时间:2019-08-30 14:40编辑:彩世界平台浏览(132)

    hdu1829 A Bug's Life(并查集)

    开两个并查集,然后合并的时候要合并两次,这样在合并之前判断是否冲突,如果不冲突就进行合并,否则不需要继续合并。

    #include
    #include
    #include
    #include
    using namespace std;
    const int MAX=2000;
    int pre[2*MAX+5];
    bool mark;
    void init(int n){
        int i;
        for(i=1;i<=MAX+n;i++) pre[i]=i;
        mark=true;
    }
    int root(int x){
        if(x!=pre[x]){
            pre[x]=root(pre[x]);
        }
        return pre[x];
    }
    void merge(int x,int y){
        int fx,fy;
        fx=root(x);
        fy=root(y-MAX);
        if(fx==fy) {
            mark=false;
            return;
        }
        fy=root(y);
        if(fx!=fy){
            pre[fx]=pre[fy];
        }
    }
    int main()
    {
        int t,i,n,m,x,y,k;
        scanf("%d",&t);
        for(i=1;i<=t;i++){
            scanf("%d%d",&n,&m);
            init(n);
            for(k=1;k<=m;k++){
                scanf("%d%d",&x,&y);
                if(mark){
                    merge(x,y+MAX);
                    merge(y,x+MAX);
                }
            }
           printf("Scenario #%d:n",i);
            if(mark){
                printf("No suspicious bugs found!n");
            }else{
                printf("Suspicious bugs found!n");
            }
            printf("n");
        }
        return 0;
    }
    

    A Bug#39;s Life(并查集) 开两个并查集,然后合并的时候要合并两次,这样在合并之前判断是否冲突,如果不冲突就进行合并,否则不需...

      题目的大意可以理解为:A爱B,B爱C ……给出一系列爱恋的关系,推断有没有同性恋。

      思路是把相同性别的归为一个集合(等价类),异性的异性为同性。

      

    图片 1图片 2

    本文由彩世界平台发布于彩世界平台,转载请注明出处:hdu1829 A Bug&amp;amp;#39;s Life(并查集)

    关键词: