并查集。

一个人拆成两个点，如果告知a和b不在一个中，那么把a,b+n并到一个集合中，把a+n,b也并到一个集合中。

询问的时候，如果a和b在一个集合中，输出在一个集合中

如果a和b+n在一个集合中，输出不在一个集合中

剩下的情况输出不确定。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;const int maxn=100000+10;int f[2*maxn];int T,n,m;int Find(int x){ if(x!=f[x]) return f[x]=Find(f[x]); return f[x];}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=2*n;i++) f[i]=i; for(int i=1;i<=m;i++) { char op[5]; scanf("%s",op); int a,b; scanf("%d%d",&a,&b); if(op[0]=='A') { int fa=Find(a),fb=Find(b),fc=Find(b+n); if(fa==fb) printf("In the same gang.\n"); else if(fa==fc) printf("In different gangs.\n"); else printf("Not sure yet.\n"); } else { int fa=Find(a),fb=Find(b+n); int fc=Find(a+n),fd=Find(b); if(fa!=fb) f[fa]=fb,f[fd]=fc; } } } return 0;}