Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <stack>
- #include <vector>
- class Vertex {
- private:
- bool visited;
- int groupNumber;
- std::vector<int> adjacent;
- public:
- Vertex(): visited(false), groupNumber(0) {
- }
- bool& isVisited() {
- return visited;
- }
- int& getGroupNumber() {
- return groupNumber;
- }
- std::vector<int>& getAdjacentVertices() {
- return adjacent;
- }
- } *vertices;
- bool compare(std::pair<std::vector<int>, std::vector<int>> *pair, std::pair<std::vector<int>, std::vector<int>> *result) {
- int i = abs((int) pair->first.size() - (int) pair->second.size()) - abs((int) result->first.size() - (int) result->second.size());
- if (i) {
- return i < 0;
- } else if (pair->first.size() != result->first.size()) {
- return pair->first.size() < result->first.size();
- }
- for (i = 0; i < pair->first.size(); i++) {
- if (pair->first[i] != result->first[i]) {
- return pair->first[i] < result->first[i];
- }
- }
- return false;
- }
- int main() {
- int n, i, j;
- std::cin >> n;
- vertices = new Vertex[n];
- std::string line;
- getline(std::cin, line);
- for (i = 0; i < n; i++) {
- getline(std::cin, line);
- for (j = 2 * n - 2; j; j -= 2) {
- if (line[j] == '+') {
- vertices[i].getAdjacentVertices().push_back(j / 2);
- }
- }
- }
- std::vector<std::pair<std::vector<int>, std::vector<int>>*> pairs;
- try {
- std::stack<int> stack;
- for (i = 0; i < n; i++) {
- if (!vertices[i].isVisited()) {
- auto pair = new std::pair<std::vector<int>, std::vector<int>>;
- pairs.push_back(pair);
- stack.push(i);
- do {
- j = stack.top();
- stack.pop();
- (vertices[j].getGroupNumber() ? pair->second : pair->first).push_back(j);
- vertices[j].isVisited() = true;
- for (const int& adjacentIndex : vertices[j].getAdjacentVertices()) {
- if (!vertices[adjacentIndex].isVisited()) {
- vertices[adjacentIndex].getGroupNumber() = !vertices[j].getGroupNumber();
- stack.push(adjacentIndex);
- } else if (vertices[adjacentIndex].getGroupNumber() == vertices[j].getGroupNumber()) {
- throw "No solution";
- }
- }
- } while (!stack.empty());
- }
- }
- } catch (const char *ex) {
- std::cout << ex;
- std::exit(0);
- }
- std::pair<std::vector<int>, std::vector<int>> *result = nullptr;
- n = pairs.size();
- for (i = (1 << n) - 1; i >= 0; i--) {
- auto pair = new std::pair<std::vector<int>, std::vector<int>>;
- for (j = 0; j < n; j++) {
- if ((i >> j) % 2) {
- pair->first.insert(pair->first.end(), pairs[j]->second.begin(), pairs[j]->second.end());
- pair->second.insert(pair->second.end(), pairs[j]->first.begin(), pairs[j]->first.end());
- } else {
- pair->first.insert(pair->first.end(), pairs[j]->first.begin(), pairs[j]->first.end());
- pair->second.insert(pair->second.end(), pairs[j]->second.begin(), pairs[j]->second.end());
- }
- }
- if (result == nullptr) {
- result = pair;
- } else if (compare(pair, result)) {
- delete result;
- result = pair;
- } else {
- delete pair;
- }
- }
- std::sort(result->first.begin(), result->first.end());
- for (int &vertexIndex : result->first) {
- std::cout << vertexIndex + 1 << " ";
- }
- delete result;
- for (auto &pair : pairs) {
- delete pair;
- }
- delete[] vertices;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement