题目地址：POJ 1182
一道很经典的种类并查集的题目。利用互相之间的关系来进行权值的维护。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; int bin[60000], rank[60000]; int find1(int x) { int y; if(bin[x]!=x) { y=bin[x]; bin[x]=find1(bin[x]); rank[x]=(rank[x]+rank[y])%3; } return bin[x]; } int main() { int n, k, p, x, y, i, flag, f1, f2, cnt=0; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { bin[i]=i; rank[i]=0; } while(k--) { flag=0; scanf("%d%d%d",&p,&x,&y); if(x>n||y>n||(p==2&&x==y)) { cnt++; continue ; } f1=find1(x); f2=find1(y); if(p==1) { if(f1==f2) { if(rank[x]!=rank[y]) cnt++; } else { bin[f2]=f1; rank[f2]=(rank[x]+3-rank[y])%3; } } else { if(f1==f2) { if(rank[x]!=(rank[y]+1)%3) cnt++; } else { bin[f2]=f1; rank[f2]=(rank[x]+2-rank[y])%3; } } } printf("%d\n",cnt); return 0; }