链接：

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82830#problem/E

 

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define maxn 100005#define oo 0xfffffffint n, T;int f[maxn], r[maxn];int Find(int x){    int k=f[x];    if(f[x]!=x)    {        f[x]=Find(f[x]);        r[x]=(r[x]+r[k])%3;    }    return f[x];}int main(){    scanf("%d%d", &n, &T);    int i, d, a, b, fa, fb, ans=0;    for(i=1; i<=n; i++)    {        f[i]=i;        r[i]=0;    }    while(T--)    {        scanf("%d%d%d",  &d, &a, &b);        fa=Find(a), fb=Find(b);        if(a>n || b>n || (d==2&&a==b))            ans++;        else if(fa==fb && (d-1+r[b])%3!=r[a])            ans++;        else if(fa!=fb)        {            f[fa]=fb;            r[fa]=((d-1)-r[a]+r[b]+3)%3;        }    }    printf("%d\n", ans);    return 0;}