UVA 10158 并查集

/* 
 * File:   UVA 10158 War
 * Author: xiaotian @ hnu
 * Created on 2010年10月9日, 上午8:56
 * 题解：并查集
 */

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#include<map>
#include<set>
#include<math.h>
using namespace std;
#define N 10008
#define inf 0x7ffffff
int father[N], b[N], n;

int Findset(int v) {
    if (v == father[v]) return v;
    int x = Findset(father[v]);
    b[v] = (b[v] + b[ father[v] ]) & 1;
    father[v] = x;
    return x;
}

int Judge(int A, int B) {
    int x = Findset(A), y = Findset(B);
    if (x != y) return 2;
    if (b[A] == b[B]) return 0;
    return 1;
}

void Union(int A, int B, int C) {
    int x = Findset(A), y = Findset(B);
    father[x] = y;
    b[x] = (C + b[A] + b[B])& 1;
    Findset(B);
}

int main(void) {
    int i, x, y, z;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i <= n; i++) father[i] = i;
        while (scanf("%d%d%d", &x, &y, &z) != EOF) {
            if (x == 0 && y == 0 && z == 0) break;
            switch (x) {
                case 1: if (Judge(y, z) == 1) puts("-1");
                    else Union(y, z, 0);
                    break;
                case 2: if (Judge(y, z) == 0) puts("-1");
                    else Union(y, z, 1);
                    break;
                case 3: if (Judge(y, z) == 0) puts("1");
                    else puts("0");
                    break;
                case 4: if (Judge(y, z) == 1) puts("1");
                    else puts("0");
                    break;
            }
        }
    }
    return 0;
}