1. 两类类别
并查集中有两类类别,即并查集中元素要么属于集合A,要么属于B,且A与B不相交。
利用向量得到关系:
1.1 POJ 2492
源代码:
#include "stdio.h" int parent[2000],relation[2000]; int find(int x) { int root,tail,temp; if(parent[x]==x) return x; else { for(root=x;parent[root]!=root;root=parent[root]); for(tail=x;tail!=root;) { temp=parent[tail]; parent[tail]=root; tail=temp; } return root; } } void update(int yroot,int n) { int i; for(i=1;i<=n;i++) { if(i!=yroot&&find(i)==yroot) relation[i]=(relation[i]+relation[yroot])%2; } } void root_union(int x,int y,int xroot,int yroot,int n) { relation[yroot]=(relation[x]-relation[y]+1)%2; update(yroot,n); parent[yroot]=xroot; } int main() { int scena_num,bug_num,intera_num,a,b,i,count; int aroot,broot,suspi_flag; scanf("%d",&scena_num); for(count=1;count<=scena_num;count++) { scanf("%d%d",&bug_num,&intera_num); suspi_flag=0; for(i=1;i<=bug_num;i++) { parent[i]=i; relation[i]=0; } while(intera_num--) { scanf("%d%d",&a,&b); aroot=find(a); broot=find(b); if(aroot!=broot) { root_union(a,aroot,bug_num); } else { if(relation[a]!=(relation[b]+1)%2) suspi_flag=1; } } if(suspi_flag==1) printf("Scenario #%d:\nSuspicIoUs bugs found!\n\n",count); else printf("Scenario #%d:\nNo suspicIoUs bugs found!\n\n",count); } return 0; }
1.2 POJ 1703
源代码:
#include "stdio.h" int parent[100000],relation[100000]; int find(int x) //寻找root结点,并更新parent链域的relation值 { int temp; if(parent[x]==x) return x; temp=parent[x]; parent[x]=find(parent[x]); relation[x]=(relation[x]+relation[temp])%2; return parent[x]; } int main() { int T,N,M,b; int aroot,broot; char message; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); for(i=1;i<=N;i++) { parent[i]=i; relation[i]=0; } while(M--) { getchar(); scanf("%c%d%d",&message,&b); aroot=find(a); broot=find(b); if(message=='A') { if(N==2&&a!=b) printf("In different gangs.\n"); else { if(aroot==broot) { if(relation[a]==relation[b]) printf("In the same gang.\n"); else printf("In different gangs.\n"); } else printf("Not sure yet.\n"); } } else { if(aroot!=broot) { parent[broot]=aroot; relation[broot]=(relation[a]-relation[b]+1)%2; } } } } return 0; }
2. 三类类别
并查集中元素属于互不相交的集合A,B,C。
类似地,可以得到如下关系:
r[y]=(r[x]+d)%3 //不能得到r[x]=(r[y]+d)%3
r[yroot]=(r[x]-r[y]+d+3)%3 //+3,是因为r[x]-r[y]+d有可能为负数
其中,0表示与root节点同类,1表示吃root节点,2表示被root节点吃。
2.1POJ 1182
源代码:
#include "stdio.h" int parent[50000],relation[50000]; int find(int x) { int temp; if(parent[x]==x) return x; temp=parent[x]; parent[x]=find(parent[x]); relation[x]=(relation[x]+relation[temp])%3; return parent[x]; } int main() { int num_ani,num_sta,statement,count=0; int a,d; scanf("%d%d",&num_ani,&num_sta); for(i=1;i<=num_ani;i++) { parent[i]=i; relation[i]=0; } while(num_sta--) { getchar(); scanf("%d%d%d",&statement,&b); d=statement-1; if(a>num_ani||b>num_ani) count++; else { aroot=find(a); broot=find(b); if(aroot!=broot) { parent[broot]=aroot; relation[broot]=(relation[a]-relation[b]+d+3)%3; } else if(relation[b]!=(relation[a]+d)%3||(d==1&&a==b)) count++; } } printf("%d\n",count); return 0; }