吧务留情qwq
题目大意：
题目大意：警察抓获N个罪犯，这些罪犯只可能属于两个团伙中的一个，现在给出M个条件（D a b表示a和b不在同一团伙），
对于每一个询问(A a b)确定a，b是不是属于同一团伙或者不能确定。
本人代码如下（我把我能省内存的都尽量省了，所以可能会有点奇怪）
#include<cstdio>
#include<cstring>
#define num(c) (c>='0'&&c<='9'?1:0)
#define N 10005
int r[N],fa[N];
int rdint() {
int i=0;
char c;
while(!num(c)) c=getchar();
for(; num(c); i=i*10+c-48,c=getchar());
return i;
}
int root(int x) {
if(!fa[x]) return x;
int t=fa[x];
fa[x]=root(fa[x]);
r[x]=(r[x]+r[t])%2;
return fa[x];
}
int main() {
for(int i=rdint(); i; i--) {
memset(fa,0,sizeof(fa));
memset(r,0,sizeof(r));
int n=rdint();
for(int j=rdint(); j; j--) {
char c;
scanf("%c",&c);
int a=rdint(),b=rdint(),x=root(a),y=root(b);
if(c=='A') puts(x==y?r[a]==r[b]?"In the same gang.":"In different gangs.":"Not sure yet.");
else {
fa[x]=y;
r[x]=(r[a]+1+r[b])%2;
}
}
}
}
#include<cstdio>
#include<cstring>
#define num(c) (c>='0'&&c<='9'?1:0)
#define N 10005
int r[N],fa[N];
int rdint() {
int i=0;
char c;
while(!num(c)) c=getchar();
for(; num(c); i=i*10+c-48,c=getchar());
return i;
}
int root(int x) {
if(!fa[x]) return x;
int t=fa[x];
fa[x]=root(fa[x]);
r[x]=(r[x]+r[t])%2;
return fa[x];
}
int main() {
for(int i=rdint(); i; i--) {
memset(fa,0,sizeof(fa));
memset(r,0,sizeof(r));
int n=rdint();
for(int j=rdint(); j; j--) {
char c;
scanf("%c",&c);
int a=rdint(),b=rdint(),x=root(a),y=root(b);
if(c=='A') puts(x==y?r[a]==r[b]?"In the same gang.":"In different gangs.":"Not sure yet.");
else {
fa[x]=y;
r[x]=(r[a]+1+r[b])%2;
}
}
}
}

大兄弟 我记得这题目是利用种类并查集 效率高一点