学步园

并查集真心高深，偏移量的问题以及路径压缩中的更新顺序问题真心把我搞迷糊了。。。。决定先不看并查集了。。。。

code：

#include <cstdio>
#include <cstring>
using namespace std;

class UFS
{
    static const int MAXN = 200001;
public:
    int father[MAXN];
    int rank[MAXN];

    void init(int num)
    {
        for(int i=0;i<=num;i++)
        {
            father[i]=i;
            rank[i]=0;
        }
    }

    int find(int k)
    {
        if(father[k]!=k)
        {
            int t=father[k];
            father[k]=find(father[k]);
            rank[k]+=rank[t];
        }
        return father[k];
    }

    void merge(int a,int b,int x,int y,int sum)
    {
        father[y]=x;
        rank[y]=rank[a]-rank[b]+sum;
    }
}ufs;

int main()
{
    int n,m,a,b,sum,i,ans;
    while(~scanf("%d%d",&n,&m))
    {
        ufs.init(n);
        ans=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&sum);
            a--;
            int x=ufs.find(a);
            int y=ufs.find(b);
            if(x!=y)
            {
                ufs.merge(a,b,x,y,sum);
            }else if(sum!=ufs.rank[b]-ufs.rank[a])
            {
                ans++;
                //printf("%d %d  %d\n",a,b,sum);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}