UVA 12232 - Exclusive-OR

题目链接

题意：有n个数字。一開始值都不知道，每次给定一个操作，I a v表示确认a值为v，I a b v,表示确认a^b = v，Q k a1 a2 a3 ... ak。表示推断这些数字的异或值是否能确定。能确定就输出值，假设有矛盾就停止

思路：带权并查集，权表示和父结点的异或值，那么多数推断的时候，仅仅要全部数字和他的父结点的异或值的异或值。假设父结点的个数是偶数个。那么依据异或的性质能抵消掉，是能够判定的。假设不为偶数，就是不能判定。

注意第一种操作，要加个小处理，就是多一个虚拟结点，保证虚拟结点始终为根。虚拟结点代表0。这样仅仅要连到虚拟结点上。第一种和另外一种操作事实上就是一样的了

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 20005;

int n, qn, parent[N], val[N], vis[N];

struct query {

    char c;

    int a, b, v, k, x[20];

} q[2 * N];

int find(int x) {

    if (x == parent[x]) return x;

    int tmp = parent[x];

    parent[x] = find(parent[x]);

    val[x] ^= val[tmp];

    return parent[x];

}

void init() {

    for (int i = 0; i <= n; i++) {

	parent[i] = i;

	val[i] = 0;

    }

    char Q[105];

    for (int i = 0; i < qn; i++) {

	scanf("%s", Q);

	q[i].c = Q[0];

	int a, b, v;

	if (Q[0] == 'I') {

	    gets(Q);

	    if (sscanf(Q, "%d%d%d", &a, &b, &v) == 2) {

		v = b; b = n;

	    }

	    q[i].a = a; q[i].b = b; q[i].v = v;

	}

	else {

	    scanf("%d", &q[i].k);

	    for (int j = 0; j < q[i].k; j++)

		scanf("%d", &q[i].x[j]);

	}

    }

}

void solve() {

    int fir = 0;

    for (int i = 0; i < qn; i++) {

	if (q[i].c == 'I') {

	    fir++;

	    int pa = find(q[i].a);

	    int pb = find(q[i].b);

	    if (pa == n) swap(pa, pb);

	    if (pa == pb) {

		if ((val[q[i].a]^val[q[i].b]) != q[i].v) {

		    printf("The first %d facts are conflicting.\n", fir);

		    return;

		}

	    }

	    else {

		parent[pa] = pb;

		val[pa] = val[q[i].a]^val[q[i].b]^q[i].v;

	    }

	}

	else {

	    int ans = 0;

	    for (int j = 0; j < q[i].k; j++) {

		int px = find(q[i].x[j]);

		ans ^= val[q[i].x[j]];

		if (px != n)

		    vis[px] ^= 1;

	    }

	    int flag = 1;

	    for (int j = 0; j < q[i].k; j++) {

		if (vis[parent[q[i].x[j]]])

		    flag = 0;

		vis[parent[q[i].x[j]]] = 0;

	    }

	    if (flag) printf("%d\n", ans);

	    else printf("I don't know.\n");

	}

    }

}

int main() {

    int cas = 0;

    while (~scanf("%d%d", &n, &qn) && n) {

	init();

	printf("Case %d:\n", ++cas);

	solve();

	printf("\n");

    }

    return 0;

}