100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
首先谢谢大神的提示,这个恐怕是最详细的了吧http://blog.csdn.net/c0de4fun/article/details/7318642
#include<stdio.h> #include<memory.h> #define MAX 50001 int father[MAX],rank[MAX]; void Init(int n){ int i; for(i=1;i<=n;i++) father[i]=i; memset(rank,0,sizeof(rank)); } int find(int x){//并查集 if(x!=father[x]){ int fx=find(father[x]); rank[x]=(rank[x]+rank[father[x]])%3; father[x]=fx; } return father[x]; } bool Union(int x,int y,int flag){ int fx,fy; fx=find(x); fy=find(y); if(fx==fy){ if((rank[y]-rank[x]+3)%3!=flag) return true; else return false; } father[fy]=fx; rank[fy]=(rank[x]-rank[y]+flag+3)%3; return false; } int main(){ int i,n,k,sum; int d,x,y; scanf("%d %d",&n,&k); Init(n); sum=0; while(k--){ scanf("%d %d %d",&d,&x,&y); if(x>n||y>n||(x==y&&d==2)) sum++; else if(Union(x,y,d-1)) sum++; } printf("%d\n",sum); return 0; }
原文:http://www.cnblogs.com/OMG-By/p/5296088.html