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:非种类并查集写法

Posted by fangcheng33 at 2024-01-22 18:02:05 on Problem 1703
In Reply To:非种类并查集写法 Posted by:omggmo at 2017-02-26 18:28:37
```> v#include <iostream>
> #include <cstdio>
> #include <cstring>
> #include <algorithm>
> using namespace std;
> const int N = 100100;
> int op[N],c[N];
> int n,m;
> int _find( int a )
> {
>     if( a==c[a] )
>         return a;
>     return c[a]=_find( c[a] );
> }
> int main()
> {
>     int t;
>     scanf("%d",&t);
>     while( t-- )
>     {
>         scanf("%d%d",&n,&m);
>         for( int i=1;i<=n;i++ )
>         {
>             c[i] = i;
>             op[i] = 0;
>         }
>         if( n==2 )
>         {
>             op[1] = 2;
>             op[2] = 1;
>         }
>         while( m-- )
>         {
>             char order[5];
>             int a,b;
>             scanf("%s%d%d",order,&a,&b);
>             if( order[0]=='D' )
>             {
>                 if( op[a]==0 )
>                     op[a] = _find( b );
>                 if( op[b]==0 )
>                     op[b] = _find( a );
>                 int fa_a = _find(a),fa_b = _find(b);
>                 c[fa_a] = _find( op[b] );
>                 c[fa_b] = _find( op[a] );
>             }
>             if( order[0]=='A' )
>             {
>                 if( _find(a)==_find(b) )
>                     printf("In the same gang.\n");
>                 else if( _find(a)==_find(op[b])||_find(b)==_find(op[a]) )
>                     printf("In different gangs.\n");
>                 else
>                     printf("Not sure yet.\n");
>             }
>         }
>     }
>     return 0;
> }
```

Followed by: