POJ_1182_并查集

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

pre构建有关系的号码的树，rel保存当前号码与根的关系，0表示相同，1表示根吃当前，2表示当前吃根。

代码中的更新公式可以先把各种情况枚举出来，然后就能推出来了。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int pre[],rel[];
//0:当前与根同类
//1:根吃当前
//2:当前吃根int findd(int x)
{
    if(pre[x] == x) return x;
    int root = findd(pre[x]);
    rel[x] = (rel[x]+rel[pre[x]])%;
    pre[x] = root;
    return root;
}
int join(int d,int x,int y)
{
    int xx = findd(x),yy = findd(y);
    if(xx == yy)
    {
        if(d ==  && rel[x] != rel[y])  return ;
        else if(d ==  && rel[y] != (rel[x]+)%)   return ;
        else return ;
    }
    pre[yy] = xx;
    rel[yy] = (rel[x]-rel[y]+d+)%;
    return ;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = ;i <= n;i++)   pre[i] = i,rel[i] = ;
    int ans = ;
    int d,x,y;
    while(m--)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x > n || y > n)  ans++;
        else if(d ==  && x == y)   ans++;
        else if(join(d,x,y))  ans++;
    }
    printf("%d\n",ans);
    return ;
}