学步园

 带权并查集的题--》  

本题详细讲解博文--》 大牛的博客

第一次接触带权并查集，集训队的人都不太会，表示这道题折腾了很长时间。。。

代码：

#include<stdio.h>
#include<string.h>
int rank[50005]= {0};
int fath[50005]= {0};
int n,k;
int cnt=0;
void init()
{
    for(int i=0; i<=n; i++)
    {
        fath[i]=i;
        rank[i]=0;
    }
}
int find(int a)
{
    if(a==fath[a])
        return a;
    int old=fath[a];    //  这里坑了我好多次   
    fath[a]=find(fath[a]);
    rank[a]=(rank[a]+rank[old])%3;
    return fath[a];
}
/*****   错误代码：  find()

int find(int a)
{
    if(a==fath[a])
        return a;
    fath[a]=find(fath[a]);
    rank[a]=(rank[a]+rank[fath[a]])%3;    这里被坑了   在上一步中，fath【a】的值已经改变了   上一步fath【a】的更新又必须在前面，所以我们应当定义一个变量old来记录他的原始值。
    return fath[a];
}

*/

/// 并查集的合并  包括权值转化 
void uion(int d,int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx==fy)
        return ;
    fath[fx]=fy;
    rank[fx]=(rank[y]+d-rank[x]+3)%3;   ///这里的权值转化表示暂时还没懂，只是从大牛们的博客中套用的。
}
void sove(int d,int a,int b)     // 不符合要求的三种情况的判断
{
    if(a>n||b>n)
    {
        cnt++;
        return ;
    }
    if(d==2&&a==b)
    {
        cnt++;
        return ;
    }
    int x=find(a);
    int y=find(b);
    if(x!=y)
        uion(d-1,a,b);
    else
    {
        if(rank[a]==((d-1)+rank[b])%3)
            uion(d-1,a,b);
        else
            cnt++;
    }
}
int main()
{
    //freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&k);
    init();
    for(int i=0; i<k; i++)
    {
        int d,a,b;
        scanf("%d%d%d",&d,&a,&b);
        sove(d,a,b);
    }
    printf("%d\n",cnt);
}