并查集+关系的传递（poj 1182）

　题目：食物链

　题意：给定一些关系.判断关系的正确性，后给出的关系服从之前的关系；

　思路：难点不在并查集，在于关系的判断，尤其是子节点与根节点的关系的判断；

　　　　这个关系看似没给出，但是给出子节点与父节点的关系AND父节点与根节点的关系之后，子节点与根节点的关系是可以确定的。

Rank[]存的是与父节点的关系，0是同类，1是被吃，2是吃

1.若Find(x) == Find(y) ,则x y有关系，直接判断关系；

　　1) d == 1, Rank[x] == Rank[y] , 否则fake++；

　　2) d == 2, x 应该是吃掉了y的，判断是否能吃掉：(Rank[x]+1)%3 == Rank[y]; 否则 fake++；

这个式子的详细如下：

2.如果Find(x) ! = Find(y);

　　则合并且设定关系，尤其是设定子节点与根节点关系：

　　注意：找父亲节点时，要不断更新 Rank[]的值。

　　这里有一个关系：如果 x 和y 为关系 r1, y 和 z 为关系 r2

那么 x 和z的关系就是（r1+r2）%3

关于合并时Rank[]值的更新：

如果 d == 1则 x和y 是同类，那么 y 对 x 的关系是 0

如果 d == 2 则 x 吃了 y, 那么 y 对 x 的关系是 1, x 对 y 的关系是 2.

综上所述 ,无论 d为1 或者是为 2, y 对 x 的关系都是 d-1

定义：fx 为 x 的根点， fy 为 y 的根节点

合并时，如果把 y 树合并到 x 树中

如何求 fy 对 fx 的r[]关系？

fy 对 y 的关系为 3-r[y]

y 对 x 的关系为 d-1

x 对 fx 的关系为 r[x]

所以 fy 对 fx 的关系是（3-r[y] + d-1 + r[x]）%3

　　　　　　　　　　　　　　理解图如下：

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std ;
#define N 50005
const double PI = acos(-1.0);
typedef long long LL ;

int root[N],Rank[N];  ///Rank存的是与父节点的关系，0是同类，1是被吃，2是吃
void Init(){
    for(int i = 0; i < N; i++){
        root[i] = i;
        Rank[i] = 0;
    }
}
int Find(int v){       ///带路径压缩的递归找根节点
    int t = root[v];
    if(root[v] != v)
        root[v] = Find(root[v]);
    Rank[v] = (Rank[v] + Rank[t])%3;
    return root[v];
}

void Union(int x, int y, int d){
    int fx = Find(x);
    int fy = Find(y);

    root[fy] = fx;      ///x 是吃 y，所以以x的根为父；
    Rank[fy] = (Rank[x] - Rank[y] + 3 +(d-1))%3;
}
int n, k, d, y, x;
int fake;
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d%d", &n, &k);
    Init();
    fake = 0;
    while(k--){
        scanf("%d%d%d", &d, &x, &y);
        if(x > n|| y > n || (d == 2 && x == y)) fake++;
        else if(Find(x) == Find(y)){
            if(d == 1 && Rank[x] != Rank[y]) fake++;
            else if(d == 2 && (Rank[x]+1)%3 != Rank[y] ) fake++;
        }else Union(x, y, d);
    }
    printf("%d
", fake);

    return 0;
}