题意是有n个数，Q个操作，你并不知道这n个数的具体值。操作有三种： 1)I p v,告诉你第p个数值为v 2)I p q v,告诉你第p个数和第q个数的异或值为v 3)Q k a1…ak，询问a1…ak这k个数的异或值 考虑并查集，par[x]保存x的父节点，v[x]保存x和par[x]的异或值。 I p q v时，合并p和q,并在寻根时路径压缩，更新父节点以及和父节点的异或值。 I p v可以视作I p 0 v，把0当做超级父节点，v[0]=0,那么v[x]=v[x]^v[0]=v。 询问时，被查询节点的根节点不是超级节点时，说明具体值未确定，只有和它同根的节点与它的异或值才是确定的，因此，统计待查询节点的根节点个数，若它不是超级父节点，且个数为奇数，那么无解。否则，有解，直接异或v[a1]^….v[ak]即为解。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define debug puts("Infinity is awesome!") #define LS (root<<1) #define RS (root<<1|1) #define LSON LS,l,mid #define RSON RS,mid+1,r #define LL long long const int Inf=1e9+7; const int maxn=2e4+5; int par[maxn], v[maxn]; void init(){ for(int i=0;i<maxn;i++){ par[i]=i; v[i]=0; } } int find(int x){ if(x==par[x]) return x; int fx=par[x]; par[x]=find(par[x]); v[x]^=v[fx]; return par[x]; } bool unite(int x,int y,int p){ int fx=find(x); int fy=find(y); if(fx==fy) return (v[x]^v[y])==p; if(fx==0) swap(fx,fy);//0 -> virtual super root par[fx]=fy; v[fx]=v[x]^v[y]^p; return true; } int main(){ int n, Q; int cas=0; int a[20], fa[20]; char ins[100]; while(~scanf("%d%d",&n,&Q)){ if(n==0&&Q==0) break; printf("Case %d:\n",++cas); init(); int facts=0, K; int x, y, val; bool err=false; for(int i=0;i<Q;i++){ scanf("%s",ins); if(ins[0]=='I'){ facts++; gets(ins); if(sscanf(ins,"%d%d%d",&x,&y,&val)==2){ val=y; y=-1; } x++, y++; if(err) continue; if(!unite(x,y,val)){ printf("The first %d facts are conflicting.\n",facts); err=true; } }else{ scanf("%d",&K); for(int j=0;j<K;j++){ scanf("%d",&a[j]); a[j]++; fa[j]=find(a[j]); } if(err) continue; fa[K]=Inf; sort(fa,fa+K); int cnt=0, no_ans=0; for(int j=0;j<K;j++){ cnt++; if(fa[j]!=fa[j+1]){ if(cnt%2==1&&fa[j]!=0) no_ans=1; else cnt=0; } } if(no_ans) { puts("I don't know."); continue; } int ans=0; for(int j=0;j<K;j++) ans^=v[a[j]]; printf("%d\n",ans); } } puts(""); } return 0; }