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;
}

• Re:非种类并查集写法 (1530) fangcheng33 2024-01-22 18:02:05