题意：食物链的弱化版本
解题关键：种类并查集，注意向量的合成。
$rank$为1代表与父亲对立，$rank$为0代表与父亲同类。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> using namespace std; typedef long long ll; #define M 100005 int fa[M],rank1[M]; int find1(int x){ if(x==fa[x]) return x; int tmp=fa[x]; fa[x]=find1(tmp); rank1[x]=(rank1[x]+rank1[tmp])%2; return fa[x]; } void unite(int x,int y){ int t=find1(x); int t1=find1(y); if(t!=t1){//合并的时候需要用到向量的合成和差 fa[t1]=t; rank1[t1]=(1-rank1[y]+rank1[x])%2; } } char ch[10]; int main(){ int T; scanf("%d",&T); while(T--){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++){ fa[i]=i; rank1[i]=0; } for(int i=0;i<m;i++){ int tmp,tmp1; scanf("%s%d%d",ch,&tmp,&tmp1); if(ch[0]=='D') unite(tmp,tmp1); else{ int x=find1(tmp); int y=find1(tmp1); if(x==y){//可以判断出关系 int r=(2-rank1[tmp]+rank1[tmp1])%2; if(r==0) printf("In the same gang. "); else printf("In different gangs. "); } else printf("Not sure yet. "); } } } return 0; }
法二：$fa$数组代表$i$属于$A$或$i$属于$B$
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> using namespace std; const int maxn=100005; int fa[maxn*2]; int find1(int x){ int r=x; while(r!=fa[r]) r=fa[r]; int i=x,j; while(i!=r){ j=fa[i]; fa[i]=r; i=j; } return r; } void unite(int x,int y){ x=find1(x),y=find1(y); if(x!=y) fa[x]=y; } int main(){ int T; scanf("%d",&T); while(T--){ int N,M,x,y; char opt[10]; scanf("%d%d",&N,&M); for(int i=0;i<=2*N;i++) fa[i]=i; while(M--){ scanf("%s%d%d",opt,&x,&y); if(opt[0]=='A'){ if(find1(x)==find1(y)) printf("In the same gang. "); else if(find1(x)==find1(y+N)&&find1(x+N)==find1(y)) printf("In different gangs. "); else printf("Not sure yet. "); } else{ unite(x,y+N); unite(x+N,y); } } } return 0; }