Advertisement
Guest User

Untitled

a guest
Jun 20th, 2019
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <stack>
  4. #include <vector>
  5.  
  6. class Vertex {
  7. private:
  8. bool visited;
  9. int groupNumber;
  10. std::vector<int> adjacent;
  11. public:
  12. Vertex(): visited(false), groupNumber(0) {
  13. }
  14. bool& isVisited() {
  15. return visited;
  16. }
  17. int& getGroupNumber() {
  18. return groupNumber;
  19. }
  20. std::vector<int>& getAdjacentVertices() {
  21. return adjacent;
  22. }
  23. } *vertices;
  24.  
  25. bool compare(std::pair<std::vector<int>, std::vector<int>> *pair, std::pair<std::vector<int>, std::vector<int>> *result) {
  26. int i = abs((int) pair->first.size() - (int) pair->second.size()) - abs((int) result->first.size() - (int) result->second.size());
  27. if (i) {
  28. return i < 0;
  29. } else if (pair->first.size() != result->first.size()) {
  30. return pair->first.size() < result->first.size();
  31. }
  32. for (i = 0; i < pair->first.size(); i++) {
  33. if (pair->first[i] != result->first[i]) {
  34. return pair->first[i] < result->first[i];
  35. }
  36. }
  37. return false;
  38. }
  39.  
  40. int main() {
  41. int n, i, j;
  42. std::cin >> n;
  43. vertices = new Vertex[n];
  44. std::string line;
  45. getline(std::cin, line);
  46. for (i = 0; i < n; i++) {
  47. getline(std::cin, line);
  48. for (j = 2 * n - 2; j; j -= 2) {
  49. if (line[j] == '+') {
  50. vertices[i].getAdjacentVertices().push_back(j / 2);
  51. }
  52. }
  53. }
  54. std::vector<std::pair<std::vector<int>, std::vector<int>>*> pairs;
  55. try {
  56. std::stack<int> stack;
  57. for (i = 0; i < n; i++) {
  58. if (!vertices[i].isVisited()) {
  59. auto pair = new std::pair<std::vector<int>, std::vector<int>>;
  60. pairs.push_back(pair);
  61. stack.push(i);
  62. do {
  63. j = stack.top();
  64. stack.pop();
  65. (vertices[j].getGroupNumber() ? pair->second : pair->first).push_back(j);
  66. vertices[j].isVisited() = true;
  67. for (const int& adjacentIndex : vertices[j].getAdjacentVertices()) {
  68. if (!vertices[adjacentIndex].isVisited()) {
  69. vertices[adjacentIndex].getGroupNumber() = !vertices[j].getGroupNumber();
  70. stack.push(adjacentIndex);
  71. } else if (vertices[adjacentIndex].getGroupNumber() == vertices[j].getGroupNumber()) {
  72. throw "No solution";
  73. }
  74. }
  75. } while (!stack.empty());
  76. }
  77. }
  78. } catch (const char *ex) {
  79. std::cout << ex;
  80. std::exit(0);
  81. }
  82. std::pair<std::vector<int>, std::vector<int>> *result = nullptr;
  83. n = pairs.size();
  84. for (i = (1 << n) - 1; i >= 0; i--) {
  85. auto pair = new std::pair<std::vector<int>, std::vector<int>>;
  86. for (j = 0; j < n; j++) {
  87. if ((i >> j) % 2) {
  88. pair->first.insert(pair->first.end(), pairs[j]->second.begin(), pairs[j]->second.end());
  89. pair->second.insert(pair->second.end(), pairs[j]->first.begin(), pairs[j]->first.end());
  90. } else {
  91. pair->first.insert(pair->first.end(), pairs[j]->first.begin(), pairs[j]->first.end());
  92. pair->second.insert(pair->second.end(), pairs[j]->second.begin(), pairs[j]->second.end());
  93. }
  94. }
  95. if (result == nullptr) {
  96. result = pair;
  97. } else if (compare(pair, result)) {
  98. delete result;
  99. result = pair;
  100. } else {
  101. delete pair;
  102. }
  103. }
  104. std::sort(result->first.begin(), result->first.end());
  105. for (int &vertexIndex : result->first) {
  106. std::cout << vertexIndex + 1 << " ";
  107. }
  108. delete result;
  109. for (auto &pair : pairs) {
  110. delete pair;
  111. }
  112. delete[] vertices;
  113. return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement