题目链接:https://www.luogu.com.cn/problem/UVA12232
对于条件 \(p \oplus q = v\),将 \(p\) 所在并查集和 \(q\) 所在并查集合并,权值为 \(d[p] \oplus d[q]\oplus v\) 即可
对于条件 \(p = v\),建立一棵虚拟节点,值为 \(0\),按上面合并即可,注意要以虚拟节点为根
查询需要保证每个并查集中需要查询的值有偶数个(虚拟节点所在并查集除外,因为虚拟节点值已知),否则不知道值是多少
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 40010;
int n, Q;
int fa[maxn], d[maxn];
int nod[maxn], cnt[maxn];
char s[100];
int find(int x){
if(fa[x] != x) {
int rt = find(fa[x]);
d[x] ^= d[fa[x]];
return fa[x] = rt;
}
else return x;
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
int kase = 0;
while(scanf("%d%d", &n, &Q) && n){
printf("Case %d:\n", ++kase);
int tot = 0;
for(int i = 0 ; i <= n ; ++i) fa[i] = i, d[i] = 0, cnt[i] = 0;
int p, q, val, k;
int omit = 0;
for(int i = 1 ; i <= Q ; ++i){
scanf("%s", s);
if(s[0] == 'I'){
++tot;
gets(s);
if(sscanf(s, "%d%d%d", &p, &q, &val) == 2){
val = q;
q = n;
}
if(omit) continue;
int u = find(p), v = find(q);
if(u == v){
if((d[p] ^ d[q]) != val){
printf("The first %d facts are conflicting.\n", tot);
omit = 1;
}
} else{
if(u == n) swap(u, v); // 以虚拟节点作为根,方便后续查询
fa[u] = v;
d[u] = (d[p] ^ d[q] ^ val);
}
} else{
scanf("%d", &k);
vector<int> rt;
rt = vector<int>();
int ans = 0;
for(int j = 1 ; j <= k ; ++j) {
scanf("%d", &nod[i]);
int u = find(nod[i]);
rt.push_back(u);
cnt[u] ^= 1;
ans ^= d[nod[i]];
}
if(omit) continue;
int flag = 0;
for(auto u : rt) {
if((cnt[u] & 1) && (u != n)) {
flag = 1;
printf("I don't know.\n");
break;
}
}
if(!flag) {
printf("%d\n", ans);
}
for(auto u : rt) cnt[u] = 0;
}
}
printf("\n");
}
return 0;
}