Hdu 3234 & Uva 12232 Exclusive-OR - c++编程基础

题意很简单，有两个操作,一个是I p q v告诉你 x[p]^x[q]=v,一个是查询k个数的异或和，问是否出现矛盾以及能否确定答案

很经典的并查集问题

首先我们可以虚拟一个根节点x[n]=0，这样所有的I p v都可以转换成 x[p]^x[n]=0.另w[a]=x[a]^x[f[a]]即本身和父节点的异或值, 那么如何合并呢？记fp=f[p],fq=f[q],x[p]^x[q]=v,另f[fp]=fq的话，w[fp]=x[fp]^x[fq]=(x[p]^x[fp])^(x[p]^x[q])^(x[q]^x[fq])=w[p]^v^w[q],由此合并。难点在查询。x[a1]^x[a2]^...^x[ak]=w[a1]^w[a2]^..^w[ak]^x[f[a1]]^x [f[a2]]^...^x[f[ak]],前一部分直接求即可，后一部分只需求父节点出现次数为奇数次的，异或起来即可

github代码

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
       using namespace std; const int N=20005; int ca,ca2,p,q,v,k,x,n,Q,f[N],w[N]; char s1[20],s2[20]; bool know,bug; int find(int x){ if(f[x]!=x){ int fx=find(f[x]); w[x]^=w[f[x]]; f[x]=fx; } return f[x]; } void Union(int x,int y,int v){ int fx=find(x); int fy=find(y); if(fx==fy){ if((w[x]^w[y])!=v) bug=true; return; } if(fx==n) swap(fx,fy); f[fx]=fy; w[fx]=w[x]^v^w[y]; //>_< } int main(){ while(scanf("%d%d",&n,&Q)&&n+Q){ ++ca; ca2=0; bug=false; for(int i=0;i<=n;++i) f[i]=i,w[i]=0; printf("Case %d:\n",ca); while(Q--){ scanf("%s",s1); if(s1[0]=='I'){ ++ca2; gets(s1); if(bug) continue; int cnt=sscanf(s1,"%d%d%d",&p,&q,&v); if(cnt==2) v=q,q=n; Union(p,q,v); if(bug) {printf("The first %d facts are conflicting.\n",ca2);continue;} } else{ know=true; scanf("%d",&k); int ans=0; map
       
        mp; while(k--){ scanf("%d",&x); int fx=find(x); ans^=w[x]; mp[fx]++; } if(bug) continue; map
        
         ::iterator it; for(it=mp.begin();it!=mp.end();it++){ if(it->second%2){ if(it->first!=n) {know=false;break;} else ans^=w[it->first]; } } if(!know) printf("I don't know.\n"); else printf("%d\n",ans); } } printf("\n"); } return 0; }