POJ1182-食物链(经典并查集)

题目链接:poj拉闸了

http://poj.org/problem?id=1182

题意：动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述： 
“1 X Y”，表示X和Y是同类。 
“2 X Y”，表示X吃Y。 
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 
1） 当前的话与前面的某些真的话冲突，就是假话； 
2） 当前的话中X或Y比N大，就是假话； 
3） 当前的话表示X吃X，就是假话。 
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

思路:各种看博客+自己思考最后终于终于终于大致上弄懂了这道题目

1.这是一道并查集的题目,但是很特殊因为当前结点与父亲结点之间还需要有一个关系(同类,吃,被吃

typedef struct
{
    int pre;
    int relation
}FATHER;

relation表示当前结点与父亲结点的关系

relation=0,1,2

0:x与父亲结点是同类

1:x吃父亲结点

2:x被父亲结点吃

注意这里的0,1,2并不是随意取的

假设输入的用d来记录

y是x的父亲结点;

d=1 d-1=0.....0表示x与y是同类

d=2 d-1=1.....1表示x吃掉y

其次在压缩路径的时候要注意更新爷爷结点与当前节点的关系

这里我们引入一个很新颖的思维,在下面合并的时候也要用到

假设结点x的父节点为rx,rx的父节点即x的爷爷结点为rrx

那么father[x].pre=rx;

        father[x].relation=i;(i为0,1,2中的一个值

        father[rx].pre=rxx;

        father[rx].relation=j;

那么,路径压缩之后rxx就是x的父节点了,我们如何根据i和j推出来rxx与x的关系呢？

答案是向量,father[rx].relation=j;j代表的是rxx->rx之间的关系,i代表的是rx->x之间的关系

根据向量的运算rxx->rx+rx->x=rxx->x,是不是很神奇..大佬想出来的

所以路径压缩之后的father[x].relation=(i+j)%3即rxx->rx+rx->x=rxx->x(模3是为了让关系值在0~2之间

那么合并的时候也是同理的,rx->x+x->y->ry=rx->ry

代码如下

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef struct
{
    int pre;
    int relation
}FATHER;
FATHER father[50010];
void Init(int k)
{
    for(int i=0;i<=k+10;i++)
    {
        father[i].pre=i;
        father[i].relation=0;
    }
}
int Find(int x);
{
    int root=x;
    while(root!=father[root].pre)
    {
        root=father[root].pre;
    }
    int temp;
    while(x!=root)
    {
        temp=father[x].pre;
        father[temp].pre=root;
        father[temp].relation=((father[temp].relation+father[x].relation)%3)  //找规律？
        x=temp;
    }
    return root;
}
int main()
{
    int N,K;
    scanf("%d %d",&N,&K);
    Init(K);
    int sum=0;
    for(int l=1;l<=N;l++)
    {
        int d,x,y;
        scanf("%d %d %d",&d,&x,&y);
        if(x>k||y<k)
        {
            sum++;
            continue;
        }
        if(d==2&&x==y)
        {
            sum++;
            break;
        }
        if()
        int rx,ry;
        rx=Find(x);
        ry=Find(y);
        if(rx!=ry)
        {
            father[rx].pre=ry;
            father[rx].relation=(father[x].relation+d-1+3-father[y].relation)%3;   //rootx->rooty=root->x+x->y+y->rooty;
        }
        else
        {
            if(d==1&&father[x].relation!=father[y].relation)
            {
                sum++;
            }
            if(d==2&&(3-father[y].relation)+father[x].relation!=1)
            {
                sum++;
            }
        }
        printf("%d\n",sum);
    }
}