UVA 10158 War

UVA_10158

和杭电那个食物链是差不多的，并且还少了一种关系的表示。

思路就是用并查集把相互产生关系的元素放到一起，并用一个数组delta[]来表示和根节点的关系，0表示friend，1表示enemy。在进行合并操作以及压缩路径的时候要注意把当前节点相对于父节点的关系用类似向量的运算转化成相对于根结点的关系。

#include<stdio.h>
#include<string.h>
#define MAXN 10010
int N, p[MAXN], delta[MAXN];
int find(int x)
{
    if(p[x] == x)
        return x;
    int tx = find(p[x]);
    delta[x] =(delta[x] + delta[p[x]]) % 2;
    p[x] = tx;
    return tx;
}
void init()
{
    int i, x, y, tx, ty, flag;
    for(i = 0; i < N; i ++)
    {
        p[i] = i;
        delta[i] = 0;
    }
    for(;;)
    {
        scanf("%d%d%d", &flag, &x, &y);
        if(!x && !y && !flag)
            break;
        tx = find(x);
        ty = find(y);
        if(flag == 3)
        {
            if(tx != ty || delta[x] != delta[y])
                printf("0\n");
            else
                printf("1\n");
        }
        else if(flag == 4)
        {
            if(tx != ty || delta[x] == delta[y])
                printf("0\n");
            else
                printf("1\n");
        }
        else if(flag == 1)
        {
            if(tx == ty)
            {
                if(delta[x] != delta[y])
                    printf("-1\n");
            }
            else
            {
                p[tx] = ty;
                delta[tx] = (delta[y] - delta[x] + 2) % 2;
            }
        }
        else if(flag == 2)
        {
            if(tx == ty)
            {
                if(delta[x] == delta[y])
                    printf("-1\n");
            }
            else
            {
                p[tx] = ty;
                delta[tx] = (delta[y] - delta[x] + 1) % 2;
            }
        }
    }
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
    }
    return 0;
}