并查集的高级应用。
与a bug‘s life 一摸一样，只是换了一个情景。
所以还是那句话，建议把食物链好好搞懂，这题也就迎刃而解了。
#include<iostream> using namespace std; #define N 100005 int p[N],r[N]; void init(int n) { for(int i=1;i<=n;i++) { p[i]=i; r[i]=0; } } int find(int x) { if(p[x]==x) return x; int temp=p[x]; p[x]=find(p[x]); r[x]=(r[x]+r[temp])%2; return p[x]; } void merge(int x,int y,int rx,int ry) { p[ry]=rx; r[ry]=(r[x]+r[y]+1)%2; } int main() { int ca,n,k,x,y,xx,yy; char chr; scanf("%d",&ca); while(ca--) { scanf("%d%d",&n,&k); getchar(); init(n); while(k--) { scanf("%c%d%d",&chr,&x,&y); getchar(); xx=find(x),yy=find(y); if(chr=='A') { if(xx!=yy) printf("Not sure yet./n"); else { if(r[x]==r[y]) printf("In the same gang./n"); else printf("In different gangs./n"); } } else merge(x,y,xx,yy); } } return 0; }
