Advertisement
Guest User

Untitled

a guest
Oct 18th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4.  
  5. int colorA, colorB;
  6.  
  7. void painting(const std::vector <std::vector <int>>& matrix,
  8.      std::vector <int>& color_of_painting, int node, int color) {
  9.     color_of_painting[node] = color; // Красим в указанный цвет
  10.     if (color_of_painting[node] == 1) { // Если он 1 то соседий красим в цвет 2
  11.         colorA += 1; // Счетчик
  12.         for (int new_node = 0; new_node < matrix[node].size(); ++new_node) { // Идем по всем ребрам из вершины
  13.             if (!color_of_painting[matrix[node][new_node]]) { // Если они ведут в бесцветную - заходим
  14.                 painting(matrix, color_of_painting, matrix[node][new_node], 2); // И рекурсивно от соседа, меняя цвет
  15.             }
  16.         }
  17.     }
  18.     if (color_of_painting[node] == 2) {
  19.         colorB += 1; // Счетчик
  20.         for (int new_node = 0; new_node < matrix[node].size(); ++new_node) {
  21.             if (!color_of_painting[matrix[node][new_node]]) {
  22.                 painting(matrix, color_of_painting, matrix[node][new_node], 1);
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28. int main() {
  29.     int number_of_nodes, degree_of_node, sum = 0; // sum - Итоговый ответ
  30.     std::ifstream fin("Nodes.txt");
  31.     fin >> number_of_nodes;  // Количество вершин
  32.     std::vector <int> color_of_painting(number_of_nodes, 0); // Вектор цветов вершин
  33.     std::vector <std::vector <int>> matrix(number_of_nodes); // Матрица смежности
  34.     for (int node_first = 0; node_first < number_of_nodes; ++node_first) {
  35.         fin >> degree_of_node; // Степень вершин, больше нигде
  36.         matrix[node_first].resize(degree_of_node);
  37.         for (int i = 0; i < degree_of_node; ++i) {
  38.             int node_second;
  39.             fin >> node_second;
  40.             matrix[node_first][i] = node_second; // Заполняем матрицу смежности
  41.         }
  42.     }
  43.     fin.close();
  44.     for (int node = 0; node < number_of_nodes; ++node) { // Идем по всем бесцветым вершинам
  45.         if (!color_of_painting[node]) {
  46.             colorA = 0; // Обнуляем 2 счетчика для счета красных и черных вершин
  47.             colorB = 0;
  48.             painting(matrix, color_of_painting, node, 1); // Идем по всему дереву увеличивая счетчики
  49.             if (colorA < colorB) { // Берем минимум на каждом этапе и увеличиваем сумму
  50.                 sum += colorA;
  51.             } else {
  52.                 sum += colorB;
  53.             }
  54.         }
  55.     }
  56.     std::cout << sum << std::endl;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement