频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
A Bug's Life hdu1829 并查集
2013-01-01 07:35:00           
收藏   我要投稿
 本题为二分的并查集,其实只要在原先的并查集基础上作一下变形。当然此题也还是有技巧的,我们可以对每个节点做个标记,若该节点与父亲节点属于同一类,则标记为,0,否则标记为1。但当我们合并两棵树时,可能会存在两棵树的标记所表达的意思完全相反,此时我们就要通过改变其中一棵树根节点的标记,来保持合并之后的树保持一致。

 

至于何时有同性恋发生,应该不难判断了,若两个节点属于同一棵树且属于同一类则发生同性恋。

 

[cpp]  

#include<iostream>  

#include<cstdio>  

  

using namespace std;  

const int maxn=2005;  

int set[maxn],flag[maxn];  

//set[i]记录i的父亲节点,flag[i]==0表示该节点的性别与父亲节点相同,否则不相同  

  

void init(int n)  

{  

    for(int i=1;i<=n;i++)  

    {  

        set[i]=i;  

        flag[i]=0;  

    }  

}  

  

int find1(int x)//返回父亲节点  

{  

    while(set[x]!=x)  

        x=set[x];  

    return x;  

}  

  

int find2(int x)//返回0或1,判断该节点与根节点是否一致  

{  

    int t=0;  

    while(set[x]!=x)  

    {  

        t^=flag[x];  

        x=set[x];  

    }  

    return t;  

}  

  

bool merge(int x,int y)//合并  

{  

    int f1=find1(x);  

    int f2=find1(y);  

    if(f1==f2)  

        return false;  

    set[f1]=f2;  

    //如果两棵树定义有冲突,则使它们一致(此处通过改变flag[f1])  

    if(find2(x)==find2(y))  

        flag[f1]^=1;  

    return true;  

}  

  

int main()  

{  

    int t,n,m,a,b,C=1;  

    bool state;  

    scanf("%d",&t);  

    while(t--)  

    {  

        scanf("%d%d",&n,&m);  

        init(n);  

        state=true;  

        while(m--)  

        {  

            scanf("%d%d",&a,&b);  

            if(!state)  

                continue;  

            if(!merge(a,b)&&(find2(a)^find2(b))==0)//同一棵树且性别相同的两个节点  

                state=false;   www.2cto.com

        }  

        printf("Scenario #%d:\n",C++);  

        if(!state)  

            printf("Suspicious bugs found!\n");  

        else  

            printf("No suspicious bugs found!\n");  

        printf("\n");//每个样例后面都换行,坑爹的地方  

    }  

    return 0;  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 查集
上一篇:c/c++ main 函数命令行参数的使用 知识小结
下一篇:模版的特化与偏特化
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站