#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>const int MAX=50005;int father[MAX];int rank[MAX];//初始化集合 void Make_Sent(int x){ father[x]=x; rank[x]=0;}//查找x的集合，回溯时压缩路径，并修改x与father[x]的关系 int Find_set(int x){ int t; if(x!=father[x]) { t = father[x]; father[x]= Find_set(father[x]); //更新x与father[X]的关系 rank[x] = (rank[x]+rank[t])%3; } return father[x];}//合并x,y所在的集合 void Union(int x,int y,int d){ int xf = Find_set(x); int yf = Find_set(y); //将集合xf合并到yf集合上 father[xf] = yf; //更新 xf 与father[xf]的关系 rank[xf]=(rank[y]-rank[x]+3+d)%3;}int main(){ int totle=0; int i,n,k,x,y,d,xf,yf; scanf("%d%d",&n,&k); for(i=1;i<=n;++i)Make_Sent(i); while(k--) { scanf("%d%d%d",&d,&x,&y); //如果x或y比n大，或x吃x，是假话 if(x>n||y>n||(d==2 && x == y)) { totle++; } else { xf = Find_set(x); yf = Find_set(y); //如果x，f的父节点相同 ，那么可以判断给出的关系是否正确的 if(xf == yf) { if((rank[x]-rank[y]+3)%3 != d-1) totle++; } else { //否则合并x，y Union(x,y,d-1); } } } printf("%dn",totle);return 0;}
