題目：給出N個數，給出一些條件，x[i]=v或者 x[i]^x[j]=k，然後給出一些詢問，x[a1]^x[a2]……
http://acm.hdu.edu.cn/showproblem.php?pid=3234
經典的並查集
類似很多題目一樣，記錄某個結點與根結點的關系，即與根結點的異或值
如果pre[a]=ra,pre[b]=rb;那麼合並之後是什麼情況呢，即r[a]=num[a]^num[ra];r[b]=num[b]^num[rb];以因為r[a]^r[b]=c
現在要求的是num[ra]=num[ra]^num[rb]=r[a]^r[b]^c;
合並就沒有問題了，但是還有個問題是，給出的條件有兩個，如果只是單個結點的該怎麼辦呢
加入一個冗余結點就行了，標號為n,值為0，任何數和0異或還為本身。
剩下的是查詢，如果查詢的某個數存在於某個集合中。
如果根為我們加入的冗余結點，那麼顯然r[x]=num[x]，直接異或起來就行了。
如果不是冗余結點，r[x]=r[x]^r[pre[x]]，則多異或了一次根結點，如果某個集合中的個數為偶數，那麼偶數次異或，剛好把根消掉，如果為奇數則說明不可判斷。
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 60005
#define N 20005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
using namespace std;
int pre[N],r[N];
int n,q;
int K,num[N];
char ope[1000];
vector<int>que;
void Init()
{
for(int i=0;i<=n;i++) pre[i]=i,r[i]=0;
}
int find(int x)
{
if(x!=pre[x])
{
int f=pre[x];
pre[x]=find(pre[x]);
r[x]^=r[f];
}
return pre[x];
}
bool Union(int a,int b,int c)
{
int ra=find(a),rb=find(b);
if(ra==rb)
{
if((r[a]^r[b])!=c) return false;
else return true;
}
if(ra==n) swap(ra,rb); //這句很重要，關系到Query的那個判斷，WA了幾次
pre[ra]=rb;
r[ra]=r[a]^r[b]^c;
return true;
}
int Query()
{
bool vis[N];mem(vis,false);
int ans=0;
for(int i=0;i<K;i++)
{
if(vis[i])continue;
int cnt=0;
int root=find(num[i]);
for(int j=i;j<K;j++)
{
if(!vis[j]&&find(num[j])==root)
{
cnt++;
vis[j]=true;
ans^=r[num[j]];
}
}
if(root!=n&&cnt&1) return -1;
}
return ans;
}
int main()
{
int CAS=0;
while(scanf("%d%d",&n,&q)!=EOF)
{
if(n==0&&q==0) break;
printf("Case %d:\n",++CAS);
Init();
bool error=false;
int cas=0;
while(q--)
{
scanf("%s",ope);
if(ope[0]=='I')
{
getchar();gets(ope);cas++;
int space=0,u,v,w;
for(int i=0;i<strlen(ope);i++) space=space+(ope[i]==' ');
if(space==1) {sscanf(ope,"%d%d",&u,&w);v=n;}
else sscanf(ope,"%d%d%d",&u,&v,&w);
if(error) continue;
if(!Union(u,v,w)){printf("The first %d facts are conflicting.\n",cas);error=true;}
}
else
{
scanf("%d",&K);
for(int i=0;i<K;i++)scanf("%d",&num[i]);
if(error) continue;
int ans=Query();
if(ans==-1) puts("I don't know.");
else printf("%d\n",ans);
}
}
puts("");
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 60005
#define N 20005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
using namespace std;
int pre[N],r[N];
int n,q;
int K,num[N];
char ope[1000];
vector<int>que;
void Init()
{
for(int i=0;i<=n;i++) pre[i]=i,r[i]=0;
}
int find(int x)
{
if(x!=pre[x])
{
int f=pre[x];
pre[x]=find(pre[x]);
r[x]^=r[f];
}
return pre[x];
}
bool Union(int a,int b,int c)
{
int ra=find(a),rb=find(b);
if(ra==rb)
{
if((r[a]^r[b])!=c) return false;
else return true;
}
if(ra==n) swap(ra,rb); //這句很重要，關系到Query的那個判斷，WA了幾次
pre[ra]=rb;
r[ra]=r[a]^r[b]^c;
return true;
}
int Query()
{
bool vis[N];mem(vis,false);
int ans=0;
for(int i=0;i<K;i++)
{
if(vis[i])continue;
int cnt=0;
int root=find(num[i]);
for(int j=i;j<K;j++)
{
if(!vis[j]&&find(num[j])==root)
{
cnt++;
vis[j]=true;
ans^=r[num[j]];
}
}
if(root!=n&&cnt&1) return -1;
}
return ans;
}
int main()
{
int CAS=0;
while(scanf("%d%d",&n,&q)!=EOF)
{
if(n==0&&q==0) break;
printf("Case %d:\n",++CAS);
Init();
bool error=false;
int cas=0;
while(q--)
{
scanf("%s",ope);
if(ope[0]=='I')
{
getchar();gets(ope);cas++;
int space=0,u,v,w;
for(int i=0;i<strlen(ope);i++) space=space+(ope[i]==' ');
if(space==1) {sscanf(ope,"%d%d",&u,&w);v=n;}
else sscanf(ope,"%d%d%d",&u,&v,&w);
if(error) continue;
if(!Union(u,v,w)){printf("The first %d facts are conflicting.\n",cas);error=true;}
}
else
{
scanf("%d",&K);
for(int i=0;i<K;i++)scanf("%d",&num[i]);
if(error) continue;
int ans=Query();
if(ans==-1) puts("I don't know.");
else printf("%d\n",ans);
}
}
puts("");
}
return 0;
}
