Leetcode-890 可能的二分法
2018-08-17 09:37:21来源:博客园 阅读 ()
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 };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 条款03:尽可能使用const 2020-01-12
- OI之路 2019-10-25
- 二分法(一):二分法的基本思想 2019-08-16
- 二分法(四):采用二分法解决“最大化平均值”问题 2019-08-16
- 二分法(二):采用二分法解决“最小化最大值问题” 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash