扩展域并查集求调

#include<numeric>
#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
#include<stdio.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int tt = 1;
struct DSU{
    vector<int>fa;
    DSU(int n):fa(2*n+1,0) {
        for(int i=1;i<=2*n;i++)
            fa[i]=i;
    }
    int find(int x) {
        while(x!=fa[x]){
            x=fa[x]=fa[fa[x]];
        }
        return x;
    }
    void merge(int x, int y) {
        x=find(x), y=find(y);
        if (x != y){
            fa[x] = y;
        }
    }
    bool same(int x, int y) {
        return find(x)==find(y);
    }
};
void solve() {
    int n, m;
    n=read(),m=read();
    vector<int>vis(n+1,0);
    DSU dsu(2*n);
    for (int i = 1; i <= m; i++) {
        char ch;
        cin>>ch;
        int a, b;
        a=read();
        b=read();
        if (ch=='D'){
            dsu.merge(a, b + n);
            dsu.merge(b, a + n);
            vis[a]=true;
            vis[b]=true;
        } else {
            if(n==2){
                cout<<"In different gangs."<<endl;
            }else{
                if ((vis[a]==false||vis[b]==false)&&(a!=b)){
                    cout<<"Not sure yet."<<endl;
                }else{
                    if(dsu.same(a, b)||dsu.same(a+n,b+n)||a==b){
                        cout<<"In the same gang."<<endl;
                    }else{
                        cout<<"In different gangs."<<endl;
                    }
                }
            }
        }
    }
}
signed main(){
    tt=read();
    while (tt--) {
        solve();
    }
    return 0;
}