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

## 非种类并查集写法

Posted by omggmo at 2017-02-26 18:28:37 on Problem 1703
```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: