POJ 2492 A Bug's Life [数据结构-并查集 union-find sets]

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 28 日

不懂请看食物链:http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/23/6272253.aspx

#include<cstdio>  
#include <cstring>  
using namespace std;  
#define MAXSIZE 50005  
int relations[MAXSIZE];  
int parent[MAXSIZE]; // 根节点  
int FindSet(int x){// 查找+递归的路径压缩  
    if( x != parent[x] )   
    {  
        int temp=parent[x];  
        parent[x] = FindSet(parent[x]);  
        relations[x]=(relations[temp]+relations[x])%2;  
    }  
    return parent[x];  
}  
void Union(int root1, int root2){  
    int x = FindSet(root1), y = FindSet(root2);  
    if( x == y ) return ;  
    parent[x] = y;  
    relations[x] = (relations[root2]-relations[root1]+1)%2;  
}  
void Initi(int n){  
    for( int i=0; i <=n+1; ++i ) { parent[i] = i; relations[i]=0;}  
}  
int main()  
{  
    freopen("1.txt","r",stdin);  
    int k,n,m,t1,t2,temp1,temp2,flag;  
    scanf("%d",&k);  
    for (int i=1;i<=k;i++)  
    {  
        flag=1;  
        scanf("%d%d",&n,&m);  
        Initi(n);  
        for (int j=0;j<m;j++)  
        {  
            scanf("%d%d",&temp1,&temp2);  
            if(flag)  
            {  
                if(FindSet(temp1)==FindSet(temp2))  
                {  
                    if(relations[temp1]!=(relations[temp2]+1)%2)  
                    flag=0;  
                }  
                else  
                    Union(temp1,temp2);  
            }  
        }  
        printf("Scenario #%d:\n",i);  
        if(flag)  
            printf("No suspicious bugs found!\n\n");  
        else printf("Suspicious bugs found!\n\n");  
    }  
}  

ps:太扯了……最后双换行贡献几个WA。。。

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日