Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <fstream>
  4. #include <iomanip>
  5. #include <time.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<pair<vector<int>, vector<int> > > teams;
  10.  
  11. bool cmp(pair<vector<int>, vector<int> > a, pair<vector<int>, vector<int> > b) {
  12. if (a.first.size() > b.first.size() && a.first.size() > b.second.size()) {
  13. return 1;
  14. }
  15. if (a.second.size() > b.first.size() && a.second.size() > b.second.size()) {
  16. return 1;
  17. }
  18. return 0;
  19.  
  20. }
  21.  
  22. //bool Search(vector<int> &color, int key)
  23. //{
  24. // for (int i = 0; i < color.size(); i++)
  25. // if (color[i] == key)
  26. // return true;
  27. // return false;
  28. //}
  29.  
  30. bool isBipart(vector<vector<int>>& g, int startNode, vector<int>& colorArr, int n)
  31. {
  32. n = g.size();
  33. colorArr[startNode] = 1;
  34. vector<int> firstTeam;
  35. vector<int> secondTeam;
  36. firstTeam.push_back(startNode);
  37.  
  38. queue <int> q;
  39. q.push(startNode);
  40.  
  41. while (!q.empty())
  42. {
  43. int v = q.front();
  44. q.pop();
  45.  
  46. // Return false if there is a self-loop
  47. //can be deleted, only for this task, because there is no self-loops
  48.  
  49. if (g[v][v])
  50. return false;
  51.  
  52. // Find all non-colored adjacent vertices
  53. for (int i = 0; i < n; i++)
  54. {
  55. //-1 - non-colored
  56. //0 - first color, 1 - second color
  57.  
  58. if (g[v][i] && colorArr[i] == -1)
  59. {
  60. colorArr[i] = 1 - colorArr[v];
  61. if (colorArr[i] == 0) {
  62. secondTeam.push_back(i);
  63. }
  64. else {
  65. firstTeam.push_back(i);
  66. }
  67. q.push(i);
  68. }
  69.  
  70. else if (g[v][i] && colorArr[i] == colorArr[v])
  71. return false;
  72. }
  73. }
  74. teams.push_back(make_pair(firstTeam, secondTeam));
  75. // If we reach here, then all adjacent vertices can
  76. // be colored with alternate color
  77. return true;
  78. }
  79.  
  80. bool isBipartite(vector<vector<int>>& g, vector<int>& color)
  81. {
  82. int n = g.size();
  83. color.assign(n, -1);
  84.  
  85. // This code is to handle disconnected graph
  86. for (int i = 0; i < n; i++)
  87. if (color[i] == -1)
  88. if (!isBipart(g, i, color, n))
  89. return false;
  90. return true;
  91. }
  92.  
  93. int main()
  94. {
  95. ifstream cin("input.in");
  96. //ofstream cout("output.out");
  97. srand(time(NULL));
  98. int n;
  99. bool _isBipartite;
  100. cin >> n;
  101. vector<vector<int>> g(n, vector<int>(n));
  102. vector<int> color(n);
  103.  
  104. for (int i = 0; i < n; i++)
  105. {
  106. for (int j = 0; j < n; j++)
  107. {
  108. int value;
  109. cin >> value;
  110.  
  111. if (i == j)
  112. continue;
  113.  
  114. if (value)
  115. g[i][j] = 0;
  116. else
  117. g[i][j] = 1;
  118. }
  119. }
  120. _isBipartite = isBipartite(g, color); // if the graph is bipartite? true / false
  121.  
  122.  
  123. if (_isBipartite)
  124. {
  125. sort(teams.begin(), teams.end(), cmp);
  126. vector<int> realFirstTeam;
  127. vector<int> realSecondTeam;
  128. int countFirstTeamMembers = 0, countSecondTeamMembers = 0; //first team - 0, second - 1.
  129. for (int i = 0; i < teams.size(); i++) {
  130. bool flag = false;
  131. if (teams[i].first.size() <= teams[i].second.size()) {
  132. flag = true;
  133. }
  134. if (realFirstTeam.size() <= realSecondTeam.size()) {
  135. if (!flag) {
  136. for (int j = 0; j < teams[i].first.size(); j++) {
  137. realFirstTeam.push_back(teams[i].first[j]);
  138. }
  139. for (int j = 0; j < teams[i].second.size(); j++) {
  140. realSecondTeam.push_back(teams[i].second[j]);
  141. }
  142. }
  143. else {
  144. for (int j = 0; j < teams[i].first.size(); j++) {
  145. realSecondTeam.push_back(teams[i].first[j]);
  146. }
  147. for (int j = 0; j < teams[i].second.size(); j++) {
  148. realFirstTeam.push_back(teams[i].second[j]);
  149. }
  150. }
  151. }
  152. else {
  153. if (!flag) {
  154. for (int j = 0; j < teams[i].first.size(); j++) {
  155. realSecondTeam.push_back(teams[i].first[j]);
  156. }
  157. for (int j = 0; j < teams[i].second.size(); j++) {
  158. realFirstTeam.push_back(teams[i].second[j]);
  159. }
  160. }
  161. else {
  162. for (int j = 0; j < teams[i].first.size(); j++) {
  163. realFirstTeam.push_back(teams[i].first[j]);
  164. }
  165. for (int j = 0; j < teams[i].second.size(); j++) {
  166. realSecondTeam.push_back(teams[i].second[j]);
  167. }
  168. }
  169. }
  170. }
  171. countFirstTeamMembers = realFirstTeam.size();
  172. countSecondTeamMembers = realSecondTeam.size();
  173. sort(realFirstTeam.begin(), realFirstTeam.end());
  174. sort(realSecondTeam.begin(), realSecondTeam.end());
  175. if (countFirstTeamMembers > 2 * countSecondTeamMembers || countSecondTeamMembers > 2 * countFirstTeamMembers)
  176. cout << "NO";
  177. else
  178. {
  179. if (countFirstTeamMembers > countSecondTeamMembers)
  180. {
  181. cout << "YES" << endl;
  182. for (int i = 0; i < realFirstTeam.size(); i++) {
  183. cout << realFirstTeam[i] + 1 << ' ';
  184. }
  185. }
  186. else
  187. {
  188. cout << "YES" << std::endl;
  189. for (int i = 0; i < realSecondTeam.size(); i++) {
  190. cout << realSecondTeam[i] + 1 << ' ';
  191. }
  192. }
  193. }
  194. }
  195. else
  196. cout << "NO" << endl;
  197. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement