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

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

Posted by D0153 at 2009-08-16 08:56:42 on Problem 3207
In Reply To:我用并查集过的,发代码! Posted by:lexdene at 2009-08-16 08:51:26
> 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