Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我用并查集过的,发代码!

Posted by lexdene at 2009-08-16 08:51:26 on Problem 3207
include <iostream>

using namespace std;

const int mymax1=500;
int root[mymax1];//等于自己的是根
bool relation[mymax1];//true是必须相同,false是必须相反

int bcj_root(int x);
bool bcj_union(int x,int y);


int main()
{
    int a[mymax1],b[mymax1];
    int n,m,i,j,temp;
    bool truth;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]>=n || b[i]>=n)
        {
            cout<<"the evil panda is lying again"<<endl;
            return 0;
        }
        if(a[i]>b[i])
        {
            temp=a[i];
            a[i]=b[i];
            b[i]=temp;
        }
    }
    for(i=0;i<m;i++)
    {
        root[i]=i;
        relation[i]=true;
    }
    truth=true;
    for(i=0;i<m && truth;i++)
    {
        for(j=0;j<i && truth;j++)
        {
            if( (a[i]-a[j]) * (a[i]-b[j]) * (b[i]-a[j]) * (b[i]-b[j] ) == 0)
            {
                cout<<"the evil panda is lying again"<<endl;
                return 0;
            }
            else if( (a[i]<a[j]&&b[i]<b[j]&&a[j]<b[i]) || (a[j] < a[i]&&b[j] < b[i]&&a[i]<b[j]))
            {
                if( !bcj_union(i,j) )
                {
                    truth=false;
                }
            }
        }
    }
    if(truth) cout<<"panda is telling the truth..."<<endl;
    else cout<<"the evil panda is lying again"<<endl;
    return 0;
}


int bcj_root(int x)
{
    if(root[x]!=x)
    {
        int temproot=root[x];
        root[x]=bcj_root(root[x]);
        relation[x]=!(relation[x] ^ relation[temproot]);
    }
    return root[x];
}

bool bcj_union(int x,int y)
{
    if(bcj_root(x)==bcj_root(y) )
    {
        if( relation[x]==relation[y] ) return false;
        else return true;
    }
    //root[y]=bcj_root(y);
    relation[bcj_root(x)]=relation[x]^relation[y];
    root[bcj_root(x)]=bcj_root(y);
    return true;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator