Poj(1182),种类并查集

题目链接：http://poj.org/problem?id=1182

再次熟练种类并查集，又积累点经验，和技巧，rank 0 2 1

先计算father[x] ,再更新rank[x];

#include <stdio.h>

int father[50010];
int rank[50010];

int Find_Set (int x)
{
    int tmp;
    if(x!=father[x])
    {
        tmp = father[x];
        father[x] = Find_Set(father[x]);        ///一定是先Find_Set，再计算rank,我这里一不小心就WA了，你必须是找到他的父节点的全值，才能计算x的权值.
        rank[x] = (rank[x]+rank[tmp])%3;
    }
    return father[x];
}

int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1; i<=N; i++)
    {
        rank[i]  = 0;
        father[i] = i;
    }

    int ans = 0;
    for(int i=0; i<M; i++)
    {
        int flag,x,y;
        scanf("%d%d%d",&flag,&x,&y);

        if((flag==2&&x==y)||x>N||y>N)
        {
            ans++;
            continue;
        }
        int fx = Find_Set(x);
        int fy = Find_Set(y);
        if(flag==1)
        {
            if(fx==fy)
            {
                if(rank[x]!=rank[y])
                    ans++;
            }
            else
            {
                father[fy] = fx;
                rank[fy] = (rank[x]-rank[y]+3)%3;   ///加上3，也没什么重要的含义咯，会模掉，k-0+3%3
            }
        }
        else
        {
            if(fx==fy)
            {
                if(rank[x]!=(rank[y]+1)%3)  ///可以吃，关系只相差1
                    ans++;
            }
            else
            {
                father[fy] = fx;
                rank[fy] = (rank[x]-rank[y]+2)%3;   ///合并，+2没什么含义咯，这样理解，就是说，0与0，下一个就是2啦，0吃2,2吃1,1吃0
            }
        }
    }
    printf("%d
",ans);
    return 0;
}