题目:UVA12232 - Exclusive-OR（带权并查集）

题目大意：给你I P V 代表Xp 的值是V。或者 I P Q V 代表X P ^X i + 1 ^X i+2 ...^X^Q = V;然后给你Q k p1 p2 p3...pk问这些数字的异或值。

解题思路：这题首先要明确 x ^ y = V , x ^ z = W, 那么 y ^ z = V ^ W; 所以这题可以用并查集来做，因为只要两个数都和同一个数异或，那么他们就属于同一个集合，这样即使它们和一个数这个数的值是未知的，但是这两个数的异或值是可以知道的。多个数的异或值也是同样的，只要这些数两两和某个相同的值异或，那么就是可以知道的，如果出现了一个失配的那么就不能求，注意这里的某个值是这个值本身是未知的，如果已知的话，那么另一个值也是可以求出来的。然后就是I P V 的情况，我们不妨给他一个虚拟的节点，这样就可以和 I P Q V 一样了。然后所有的数和0的异或还是本身，所以初值是0.这题要求如果出现了两个事实相饽的，那么后面的也就不要再做了。

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int N = 2e4 + 5; const int maxn = 4e4 + 5; int n, Q; int p[N]; int v[N]; struct Query { char type; int a, b, val; int k, l[100]; } q[maxn]; void init () { for (int i = 0; i <= n; i++) { p[i] = i; v[i] = 0; } } int getParent (const int a) { if (a == p[a]) return a; int t = p[a]; p[a] = getParent (p[a]); v[a] ^= v[t]; return p[a]; } void solve () { int cnt = 0; for (int i = 1; i <= Q; i++) { if (q[i].type == 'I') { cnt++; int p1 = getParent (q[i].a); int p2 = getParent (q[i].b); if (p1 == p2) { if ((v[p1] ^ v[q[i].a] ^ v[q[i].b]) != q[i].val) { printf ("The first %d facts are conflicting.\n", cnt); return; } } else { if (p1 == n) swap (p1, p2); p[p1] = p2; v[p1] = (v[q[i].a] ^ v[q[i].b] ^ q[i].val); } } else { int ans = 0; int parent[N]; bool flag = 1; memset (parent, 0, sizeof (parent)); for (int j = 0; j < q[i].k; j++) { getParent (q[i].l[j]); ans ^= v[q[i].l[j]]; if (p[q[i].l[j]] != n) parent[p[q[i].l[j]]] ^= 1; } for (int j = 0; j <= n; j++) { if (parent[j]) { flag = 0; break; } } if (flag) printf ("%d\n", ans); else printf ("I don't know.\n"); } } } int main () { char str[105]; int a, b, val; int cas = 0; while (scanf ("%d%d", &n, &Q) && (n || Q)) { init (); printf ("Case %d:\n", ++cas); for (int i = 1; i <= Q; i++) { scanf ("%s", str); q[i].type = str[0]; if (q[i].type == 'I') { gets(str); if (sscanf (str, "%d%d%d", &q[i].a, &q[i].b, &q[i].val) == 2) { q[i].val = q[i].b; q[i].b = n; } } else { scanf ("%d", &q[i].k); for (int j = 0; j < q[i].k; j++) scanf ("%d", &q[i].l[j]); } } solve(); printf ("\n"); } return 0; }