Leetcode-890 可能的二分法

  1 struct UnionFindSet
  2 {
  3     int *ID;
  4     int *Auxiliary;
  5     int GroupSum;
  6     int WeightOriginalTotal;
  7 };
  8 
  9 struct UnionFindSet* UnionFindSetInit(int WeightTotal)
 10 {
 11     struct UnionFindSet *UFSet = (struct UnionFindSet *)malloc(sizeof(struct UnionFindSet));
 12     
 13     UFSet -> GroupSum = WeightTotal;
 14     UFSet -> WeightOriginalTotal = WeightTotal;
 15     
 16     UFSet -> ID = (int*)malloc(WeightTotal*sizeof(int));
 17     UFSet -> Auxiliary = (int*)malloc(WeightTotal*sizeof(int));
 18     
 19     int i;
 20     for(i = 0;i < WeightTotal;i ++)
 21     {
 22         UFSet -> ID[i] = i;
 23     }
 24     for(i = 0;i < WeightTotal;i ++)
 25     {
 26         UFSet -> Auxiliary[i] = 1;
 27     }
 28     
 29     return UFSet; 
 30 }
 31 
 32 int UnionFindSetFind(struct UnionFindSet* UFSet,int WeightNum)
 33 {
 34     if(WeightNum>UFSet -> WeightOriginalTotal-1 || WeightNum<0)
 35     {
 36         return -1;
 37     }
 38     
 39     while(WeightNum != UFSet -> ID[WeightNum])
 40     {
 41         WeightNum = UFSet -> ID[WeightNum];
 42     }
 43     return WeightNum;
 44 }
 45 
 46 int UnionFindSetUnion(struct UnionFindSet* UFSet,int Weight_1,int Weight_2)
 47 {
 48     int WeightRoot_1 = UnionFindSetFind(UFSet,Weight_1);
 49     int WeightRoot_2 = UnionFindSetFind(UFSet,Weight_2);
 50     
 51     if(WeightRoot_1 == -1 || WeightRoot_2 == -1)
 52     {
 53         return -1;
 54     }
 55     if(WeightRoot_1 == WeightRoot_2)
 56     {
 57         return 1;
 58     }
 59     
 60     if(UFSet -> Auxiliary[WeightRoot_1] < UFSet -> Auxiliary[WeightRoot_2])
 61     {
 62         UFSet -> ID[WeightRoot_1] = WeightRoot_2;
 63         UFSet -> Auxiliary[WeightRoot_2] += UFSet -> Auxiliary[WeightRoot_1];
 64     }
 65     else
 66     {
 67         UFSet -> ID[WeightRoot_2] = WeightRoot_1;
 68         UFSet -> Auxiliary[WeightRoot_1] += UFSet -> Auxiliary[WeightRoot_2];
 69     }
 70     
 71     UFSet -> GroupSum --;
 72     return 0;
 73 }
 74 
 75 bool UnionFindSetIsConnected(struct UnionFindSet* UFSet,int Weight_1,int Weight_2)
 76 {
 77     return (UnionFindSetFind(UFSet,Weight_1) == UnionFindSetFind(UFSet,Weight_2));
 78 }
 79 
 80 class Solution
 81 {
 82     public:
 83         bool possibleBipartition(int N, vector<vector<int>>& dislikes)
 84         {
 85             if(N==1)
 86                 return true;
 87             struct UnionFindSet *UFSet1 = UnionFindSetInit(2000);
 88             struct UnionFindSet *UFSet2 = UnionFindSetInit(2000);
 89             vector<pair<int,int>> left;
 90             UnionFindSetUnion(UFSet1,dislikes[0][0],0);
 91             UnionFindSetUnion(UFSet2,dislikes[0][1],0);
 92             
 93             for(auto p:dislikes)
 94             {
 95                 if(UnionFindSetIsConnected(UFSet1,p[0],0))
 96                 {
 97                     if(UnionFindSetIsConnected(UFSet1,p[1],0))
 98                     {
 99                         return false;
100                     }
101                     UnionFindSetUnion(UFSet2,p[1],0);
102                 }
103                 else if(UnionFindSetIsConnected(UFSet2,p[0],0))
104                 {
105                     if(UnionFindSetIsConnected(UFSet2,p[1],0))
106                     {
107                         return false;
108                     }
109                     UnionFindSetUnion(UFSet1,p[1],0);
110                 }
111                 else if(UnionFindSetIsConnected(UFSet1,p[1],0))
112                 {
113                     if(UnionFindSetIsConnected(UFSet1,p[0],0))
114                     {
115                         return false;
116                     }
117                     UnionFindSetUnion(UFSet2,p[0],0);
118                 }
119                 else if(UnionFindSetIsConnected(UFSet2,p[1],0))
120                 {
121                     if(UnionFindSetIsConnected(UFSet2,p[0],0))
122                     {
123                         return false;
124                     }
125                     UnionFindSetUnion(UFSet1,p[0],0);
126                 }
127                 else
128                 {
129                     left.push_back(make_pair(p[0],p[1]));
130                 }
131             }
132             for(auto p:left)
133             {
134                 if(UnionFindSetIsConnected(UFSet1,p.first,p.second)
135                 || UnionFindSetIsConnected(UFSet2,p.first,p.second))
136                     return false;
137             }
138             return true;
139         }
140 };