虚拟一个根节点n,设其值为0.并且始终保持其为根。
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Maxn 40010 #define Maxm 100010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 0x7fffffff #define Mod 1000000007 using namespace std; int fa[Maxn],val[Maxn],n; map<int,int> num; void init() { for(int i=0;i<Maxn;i++){ fa[i]=i; val[i]=0; } } int find(int x) { if(fa[x] == x) return x; int t = find(fa[x]); val[x] ^= val[fa[x]]; fa[x] = t; return t; } int merg(int a,int b,int v) { int x=find(a); int y=find(b); if(x==y){ return (val[a]^val[b])==v; } //cout<<x<<" * "<<y<<endl; if(x==n){ fa[y]=x; val[y]=val[a]^val[b]^v; return 1; } if(y==n){ fa[x]=y; val[x]=val[a]^val[b]^v; return 1; } fa[x]=y; val[x]=val[a]^val[b]^v; return 1; } int main() { int q,i,j,x,y,v,cnt=0,k,ans,ok,Case=0; char str[20],ch[5]; while(scanf("%d%d",&n,&q)!=EOF,n||q){ init(); int err=0; cnt=0; printf("Case %d: ",++Case); for(i=1;i<=q;i++){ scanf("%s",ch); if(ch[0]=='I'){ gets(str); if(err) continue; ++cnt; if(sscanf(str,"%d %d %d",&x,&y,&v)==2){ v=y; y=n; //cout<<x<<" "<<y<<" "<<v<<endl; if(!merg(x,y,v)){ err=1,printf("The first %d facts are conflicting. ",cnt); } } else { //cout<<x<<" "<<y<<" "<<v<<endl; if(!merg(x,y,v)){ err=1,printf("The first %d facts are conflicting. ",cnt); } } } else { scanf("%d",&k); ans=0; ok=0; num.clear(); for(j=1;j<=k;j++){ scanf("%d",&x); if(err) continue; int t=find(x); ans^=val[x]; //cout<<t<<" "<<x<<" "<<find(0)<<endl; if(t!=n){ if(num[t]%2==0){ ok++; num[t]++; }else ok--,num[t]--; } } if(err) continue; if(!ok){ printf("%d ",ans); }else{ printf("I don't know. "); } } } printf(" "); } return 0; }