test-7-G

//#include<bits/stdc++.h>//解1: 直接合并,c数组存和根节点的关系。 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=1e6; int fa[N+100],c[N+100]; void init(int n){for(int i=1;i<=n;i++)fa[i]=i;} int found(int x) { if(x==fa[x]) return x; int father=fa[x]; //c[x]=(c[father]+c[x])%2;//0-0->0,1-1->0,1-0/0-1->1(画图可知) fa[x]=found(fa[x]); c[x]=(c[father]+c[x])%2;//0-0->0,1-1->0,1-0/0-1->1/*位置不能放上面,要递归*/ return fa[x]; } void Union(int x,int y) { int tx=found(x),ty=found(y); if(tx==ty) return; fa[tx]=ty; if((c[x]+c[y])%2==0) c[tx]=1;//0-0->1,1-1->1,0-1/1-0->0（x,y是对立关系,值画图可知） //else c[tx]=0;/*可以加上呦*/ } int main() { int t; scanf("%d",&t); while(t--) { memset(c,0,sizeof(c)); int n,m; scanf("%d%d",&n,&m); init(n); while(m--) { char str[3];int x,y; scanf("%s%d%d",str,&x,&y); if(str[0]=='D') { Union(x,y); } else { if(found(x)!=found(y)){printf("Not sure yet.\n");} else { if(c[x]==c[y]){printf("In the same gang.\n");} else printf("In different gangs.\n"); } } } } return 0; } #include<iostream>//解2:自己想的思路,合并同组关系,b数组存敌对组（集合） #include<cstdio> #include<cstring> using namespace std; const int N=1e5; int fa[N+100],b[N+100]; void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; } int found(int x) { if(x==fa[x]) return x; return fa[x]=found(fa[x]); } void Union(int x,int y) { int tx=found(x),ty=found(y); if(tx!=ty) fa[tx]=ty; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); init(n); memset(b,0,sizeof(b)); for(int i=0;i<m;i++) { char str[3]; int x,y; scanf("%s%d%d",str,&x,&y); if(str[0]=='D') { if(b[x]) Union(b[x],y); if(b[y]) Union(b[y],x); b[x]=found(y); b[y]=found(x); } else { //for(int i=1;i<=n;i++) printf("%d ",b[i]);printf("\n"); //for(int i=1;i<=n;i++) printf("%d ",found(i));printf("\n"); //if(n==2){printf("In different gangs.\n");continue;} int tx=found(x),ty=found(y); if(tx==ty){printf("In the same gang.\n");continue;} if(tx==found(b[y])||ty==found(b[x])) {printf("In different gangs.\n");continue;} /*大致是路径压缩时的问题,使b数组最终存的不都是根节点wr惨了*/ printf("Not sure yet.\n"); } } } return 0; } #include<iostream>//解3:x代表a集团,x+n集团,同理y; #include<cstdio> #include<cstring> using namespace std; const int N=1e5; int fa[2*N+100]; void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; } int found(int x) { if(x==fa[x]) return x; return fa[x]=found(fa[x]); } void Union(int x,int y) { int tx=found(x),ty=found(y); if(tx!=ty) {fa[tx]=ty;} } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); init(2*n); for(int i=0;i<m;i++) { char str[3]; int x,y; scanf("%s%d%d",str,&x,&y); if(str[0]=='D') { Union(x+n,y); Union(x,y+n); } else { //if(n==2){printf("In different gangs.\n");continue;} if(found(x)==found(y)||found(x+n)==found(y+n)) printf("In the same gang.\n"); else if(found(x)==found(y+n)||found(y)==found(x+n)) printf("In different gangs.\n"); else printf("Not sure yet.\n"); } } } return 0; } Find them, Catch them

附数据：

123 9 123 D 1 2 D 2 3 D 4 5 D 5 6 D 7 8 D 8 9 A 1 7 D 6 9 D 3 5 A 1 7