HDU 3234 Exclusive-OR 09年武汉区域赛E题

又是一道神奇的并查集，话说以前在POJ上做并查集，就使用过所谓偏移向量，儿子跟父亲的关系用一个向量值表示出来，然后儿子和儿子之间的关系也能通过一些向量关系转化，而这道题也应该是并查集的偏移向量的运用，只不过复杂了那么一点，变成了异或运算，然后插入的时候有一些小的精妙想法，后来看别人的思路才发现，真是惭愧之极，这样才AC了。

插入的时候，会出现两个数，或者三个数的情况，其实都可以转化为三个数，我们都知道一个数跟0的异或值都是他本身，那么只要把赋值运算等价于跟一个值为0的节点异或就行了，不妨设这个节点为n，然后互相有关系的都放到一个集合里，我们观察偏移向量可以得知，实际上一些节点的异或值可以转化为他们与父亲节点的异或值再一起异或，如果父亲节点的个数是偶数，那么显然对结果无影响，如果是奇数，只要父亲节点的值知道，那么也是能算出来的，那么我们在并查集的并操作中，因为标号n的节点值已经知道，所以尽量要让他成为父亲节点，这样的话，所有已经赋值的节点都在n的集合内，显然，如果出现已知两个节点的异或值和一个节点的值，求另一个节点的值时，那么由于这个节点的父亲节点是n，那么只要和这个点相关的节点都和n的集合合并，值也就出来了，就这样，只要值知道的节点都会在n集合内，父节点不是n的节点的值必然不知道。那么最后也就好判断了。

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 500005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n, delta[20005];
int father[20005];
void init()
{
    for(int i = 0; i <= n; i++)
    {
        father[i] = i;
        delta[i] = 0;
    }
}
int find(int x)
{
    if(father[x] == x)
    return x;
    int t = find(father[x]);
    delta[x] ^= delta[father[x]];
    father[x] = t;
    return t;
}
bool join(int x, int y, int v)
{
    int fx = find(x);
    int fy = find(y);
    if(fx == fy)
    {
        return v == (delta[x] ^ delta[y]);
    }
    else if(fx == n)
    {
        father[fy] = fx;
        delta[fy] = delta[x] ^ delta[y] ^ v;
    }
    else if(fy == n)
    {
        father[fx] = fy;
        delta[fx] = delta[x] ^ delta[y] ^ v;
    }
    else
    {
        father[fx] = fy;
        delta[fx] = delta[x] ^ delta[y] ^ v;
    }
    return 1;
}
int main()
{
#ifdef LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    int i, j, q, x, y, v, k, tmp, ca = 1;
    char s[105];
    char nu[5];
    while(scanf("%d%d", &n, &q) != EOF)
    {
        if(n == 0 && q == 0) break;
        bool error = false;
        init();
        int fact = 0;
        printf("Case %d:\n",ca++);
        while(q--)
        {
            scanf("%s", nu);
            if(nu[0] == 'I')
            {
                fact++;
                gets(s);
                if(error) continue;
                int ct = sscanf(s, "%d %d %d", &x, &y, &v);
                if(ct == 2)
                {
                    v = y;
                    y = n;
                    if(!join(x, y, v))
                    {
                        error = true;
                        printf("The first %d facts are conflicting.\n", fact);
                    }
                }
                else
                {
                    if(!join(x, y, v))
                    {
                        error = true;
                        printf("The first %d facts are conflicting.\n", fact);
                    }
                }
            }
            else
            {
                scanf("%d", &k);
                map<int, int>mp;
                int ans = 0;
                bool can = true;
                for(i = 0; i < k; i++)
                {
                    scanf("%d", &tmp);
                    if(error) continue;
                    int t = find(tmp);
                    mp[t]++;
                    ans ^= delta[tmp];
                }
                map<int, int>::iterator it;
                for(it = mp.begin(); it != mp.end(); it++)
                {
                    if(it -> second % 2) //该父节点出现了奇数次
                    {
                        if(it -> first != n) //如果父节点是n，说明值知道，否则就不知道了
                        {
                            can = false;
                            break;
                        }
                    }
                }
                if(error) continue;
                if(can)
                printf("%d\n", ans);
                else printf("I don't know.\n");
            }
        }
        puts("");
    }
    return 0;
}