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

## Re:WA的童鞋进！！！！（附代码）

Posted by froest at 2012-04-13 17:41:37 on Problem 1703
In Reply To:WA的童鞋进！！！！（附代码） Posted by:speedcell4 at 2011-08-01 21:45:17
```> 测下这组数据
> 1
> 2 1
> A 1 2
> 答案应该是In different gangs.
> 就因为这个……WA到死……
>
> #include<iostream>
> #define SIZE 100010
> using namespace std;
> int tcase;
> int n,m,x,y;
> char ctrl;
> struct node
> {
>     int pa;
>     int ki;
> }a[SIZE];
> void Init(int n)
> {
>     for(int i=1;n-i>=0;i++)
>     {
>         a[i].pa=i;
>         a[i].ki=0;
>     }
> }
> int findPa(int n)
> {
>     if(a[n].pa!=n)
>     {
>         int Pa=a[n].pa;
>         int Root=findPa(a[n].pa);
>         a[n].ki=(a[n].ki+a[Pa].ki)%2;
>         return a[n].pa=Root;
>     }
>     else return n;
> }
> void Union(int x,int y)
> {
>     int xx=findPa(x);
>     int yy=findPa(y);
>     a[xx].pa=yy;
>     a[xx].ki=(a[y].ki-a[x].ki+1+2)%2;
> }
> int main()
> {
>     scanf("%d",&tcase);while(tcase--)
>     {
>         scanf("%d %d",&n,&m);getchar();
>         Init(n);
>         for(int i=0;m-i>0;i++)
>         {
>             scanf("%c %d %d",&ctrl,&x,&y);getchar();
>             if(n==2&&ctrl=='A') printf("In different gangs.\n");
>             else if(ctrl=='D')
>             {
>                 Union(x,y);
>             }
>             else
>             {
>                 int xx=findPa(x);
>                 int yy=findPa(y);
>                 if(xx!=yy) printf("Not sure yet.\n");
>                 else if(a[x].ki==a[y].ki) printf("In the same gang.\n");
>                 else printf("In different gangs.\n");
>             }
>         }
>     }
>     return 0;
> }

Followed by: