quick-find-白红宇

quick-find

阅读量：5209 次

发布时间：2019-06-14

本文共 2089 字，大约阅读时间需要 6 分钟。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         struct UnionFindSet{    int *ID;    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));        int i;    for(i = 0;i < WeightTotal;i ++)    {        UFSet -> ID[i] = i;    }        return UFSet; }int UnionFindSetFind(struct UnionFindSet* UFSet,int WeightNum){    if(WeightNum>UFSet -> WeightOriginalTotal-1 || WeightNum<0)    {        return -1;    }    return UFSet -> ID[WeightNum];}//return 1 if two are in the same weight,return 0 if everything ok,return -1 if ERRORint UnionFindSetUnion(struct UnionFindSet* UFSet,int Weight_1,int Weight_2){    int ID_1 = UnionFindSetFind(UFSet,Weight_1);    int ID_2 = UnionFindSetFind(UFSet,Weight_2);        if(ID_1 == -1 || ID_2 == -1)    {        return -1;    }    if(ID_1 == ID_2)    {        return 1;    }        int i;        for(i = 0;i < UFSet -> WeightOriginalTotal;i ++)    {        if(UFSet -> ID[i] == ID_1)        {            UFSet -> ID[i] = ID_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);    UnionFindSetUnion(UFSet,3,8);    UnionFindSetUnion(UFSet,6,5);    UnionFindSetUnion(UFSet,9,4);    UnionFindSetUnion(UFSet,2,1);    UnionFindSetUnion(UFSet,8,9);    UnionFindSetUnion(UFSet,5,0);    UnionFindSetUnion(UFSet,7,2);    UnionFindSetUnion(UFSet,6,1);    UnionFindSetUnion(UFSet,1,0);    UnionFindSetUnion(UFSet,6,7);        bool Result = UnionFindSetIsConnected(UFSet,0,1);    printf("%d\n",Result);    return 0;}