虚拟一个根节点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=;i<Maxn;i++){
fa[i]=i;
val[i]=;
}
}
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 ;
}
if(y==n){
fa[x]=y;
val[x]=val[a]^val[b]^v;
return ;
}
fa[x]=y;
val[x]=val[a]^val[b]^v;
return ;
}
int main()
{
int q,i,j,x,y,v,cnt=,k,ans,ok,Case=;
char str[],ch[];
while(scanf("%d%d",&n,&q)!=EOF,n||q){
init();
int err=;
cnt=;
printf("Case %d:\n",++Case);
for(i=;i<=q;i++){
scanf("%s",ch);
if(ch[]=='I'){
gets(str);
if(err) continue;
++cnt;
if(sscanf(str,"%d %d %d",&x,&y,&v)==){
v=y;
y=n;
//cout<<x<<" "<<y<<" "<<v<<endl;
if(!merg(x,y,v)){
err=,printf("The first %d facts are conflicting.\n",cnt);
}
}
else {
//cout<<x<<" "<<y<<" "<<v<<endl;
if(!merg(x,y,v)){
err=,printf("The first %d facts are conflicting.\n",cnt);
}
}
}
else {
scanf("%d",&k);
ans=;
ok=;
num.clear();
for(j=;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]%==){
ok++;
num[t]++;
}else ok--,num[t]--;
}
}
if(err) continue;
if(!ok){
printf("%d\n",ans);
}else{
printf("I don't know.\n");
}
}
}
printf("\n");
}
return ;
}