POJ 1703 Find them, Catch them [数据结构-并查集 union-find sets]

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

十分类似POJ2492 a bug‘s life,稍微修改一下即可提交。2492见http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/28/6283849.aspx

#include<cstdio>    
#include <cstring>    
using namespace std;    
#define MAXSIZE 100005    
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,temp1,temp2,flag;    
    char ch;  
    scanf("%d",&k);    
    for (int i=1;i<=k;i++)    
    {    
        flag=1;    
        scanf("%d%d",&n,&m);    
        getchar();  
        Initi(n);    
        for (int j=0;j<m;j++)    
        {    
            scanf("%c%d%d",&ch,&temp1,&temp2);    
            getchar();  
            if(ch=='A')  
            {  
                if (FindSet(temp1)!=FindSet(temp2)) printf("Not sure yet.\n");  
                else if (relations[temp1]==relations[temp2]) printf("In the same gang.\n");  
                else  printf("In different gangs.\n");  
                /*if(FindSet(temp1)==FindSet(temp2) && relations[temp1]!=(relations[temp2]+1)%2)   
                    printf("In the same gang.\n"); 
                else if(relations[temp1]==(relations[temp2]+1)%2) 
                    printf("In different gangs.\n"); 
                else printf("Not sure yet.\n");*/  
            }  
            else /*if(FindSet(temp1) !=FindSet(temp2))*/  
                Union(temp1,temp2);    
        }    
    }    
}    

我猜你可能也喜欢:

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 月 21 日