记录编号	443366	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]食物链	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2017-08-30 16:17:58	内存使用	0.70 MiB

#include <stdio.h>
#include <cstring>
#include <iostream>
using std::swap;
const int MAXN = 50005;
int n,m,type,x,y,Ans;
int fa[MAXN],w[MAXN];


template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

int find(int x){
    if(fa[x] == x) return fa[x];
    register int re = fa[x];
    fa[x] = find(fa[x]);
    w[x] += w[re];
    return fa[x];
}

inline bool link(int x,int y,int W){
    register int fa_x = find(x) , fa_y = find(y);
    if(fa_x == fa_y){return (((w[x]+W)%3+3)%3) != ((w[y]%3+3)%3);}
    fa[fa_y] = fa_x;
    w[fa_y] = w[x] - w[y] + W;
    return 0;
}

int main(){
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    n = read<int>(); m = read<int>();
    for(int i = 1;i<=n;i++) fa[i] = i;
    while(m--){
        type = read<int>();
        x = read<int>(),y = read<int>();
        if((x>n)||(y>n)||(type == 2&& x == y)){++Ans;continue;}
        Ans += link(x,y,type-1);
    }
    printf("%d\n",Ans);
}