#include <stdio.h> #include <malloc.h> #include <stdbool.h> #include <string.h> struct UnionFindSet { int *ID; int *Auxiliary; int GroupSum; int WeightOriginalTotal; }; struct UnionFindSet* UnionFindSetInit(int WeightTotal) { struct UnionFindSet *UFSet = malloc(sizeof(struct UnionFindSet)); UFSet -> GroupSum = WeightTotal; UFSet -> WeightOriginalTotal = WeightTotal; UFSet -> ID = malloc(WeightTotal*sizeof(int)); UFSet -> Auxiliary = malloc(WeightTotal*sizeof(int)); int i; for(i = 0;i < WeightTotal;i ++) { UFSet -> ID[i] = i; } for(i = 0;i < WeightTotal;i ++) { UFSet -> Auxiliary[i] = 1; } return UFSet; } int UnionFindSetFind(struct UnionFindSet* UFSet,int WeightNum) { if(WeightNum>UFSet -> WeightOriginalTotal-1 || WeightNum<0) { return -1; } while(WeightNum != UFSet -> ID[WeightNum]) { WeightNum = UFSet -> ID[WeightNum]; } return WeightNum; } int UnionFindSetUnion(struct UnionFindSet* UFSet,int Weight_1,int Weight_2) { int WeightRoot_1 = UnionFindSetFind(UFSet,Weight_1); int WeightRoot_2 = UnionFindSetFind(UFSet,Weight_2); if(WeightRoot_1 == -1 || WeightRoot_2 == -1) { return -1; } if(WeightRoot_1 == WeightRoot_2) { return 1; } if(UFSet -> Auxiliary[WeightRoot_1] < UFSet -> Auxiliary[WeightRoot_2]) { UFSet -> ID[WeightRoot_1] = WeightRoot_2; UFSet -> Auxiliary[WeightRoot_2] += UFSet -> Auxiliary[WeightRoot_1]; } else { UFSet -> ID[WeightRoot_2] = WeightRoot_1; UFSet -> Auxiliary[WeightRoot_1] += UFSet -> Auxiliary[WeightRoot_2]; } UFSet -> GroupSum --; return 0; } bool UnionFindSetIsConnected(struct UnionFindSet* UFSet,int Weight_1,int Weight_2) { return (UnionFindSetFind(UFSet,Weight_1) == UnionFindSetFind(UFSet,Weight_2)); } int main() { int i; struct UnionFindSet *UFSet = UnionFindSetInit(10); UnionFindSetUnion(UFSet,4,3); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,3,8); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,6,5); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,9,4); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,2,1); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,8,9); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,5,0); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,7,2); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,6,1); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,1,0); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); UnionFindSetUnion(UFSet,6,7); for(i = 0;i < 10;i ++) printf("%d ",UFSet->ID[i]); printf(" "); bool Result = UnionFindSetIsConnected(UFSet,0,1); printf("%d ",Result); return 0; }