Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- int colorA, colorB;
- void painting(const std::vector <std::vector <int>>& matrix,
- std::vector <int>& color_of_painting, int node, int color) {
- color_of_painting[node] = color; // Красим в указанный цвет
- if (color_of_painting[node] == 1) { // Если он 1 то соседий красим в цвет 2
- colorA += 1; // Счетчик
- for (int new_node = 0; new_node < matrix[node].size(); ++new_node) { // Идем по всем ребрам из вершины
- if (!color_of_painting[matrix[node][new_node]]) { // Если они ведут в бесцветную - заходим
- painting(matrix, color_of_painting, matrix[node][new_node], 2); // И рекурсивно от соседа, меняя цвет
- }
- }
- }
- if (color_of_painting[node] == 2) {
- colorB += 1; // Счетчик
- for (int new_node = 0; new_node < matrix[node].size(); ++new_node) {
- if (!color_of_painting[matrix[node][new_node]]) {
- painting(matrix, color_of_painting, matrix[node][new_node], 1);
- }
- }
- }
- }
- int main() {
- int number_of_nodes, degree_of_node, sum = 0; // sum - Итоговый ответ
- std::ifstream fin("Nodes.txt");
- fin >> number_of_nodes; // Количество вершин
- std::vector <int> color_of_painting(number_of_nodes, 0); // Вектор цветов вершин
- std::vector <std::vector <int>> matrix(number_of_nodes); // Матрица смежности
- for (int node_first = 0; node_first < number_of_nodes; ++node_first) {
- fin >> degree_of_node; // Степень вершин, больше нигде
- matrix[node_first].resize(degree_of_node);
- for (int i = 0; i < degree_of_node; ++i) {
- int node_second;
- fin >> node_second;
- matrix[node_first][i] = node_second; // Заполняем матрицу смежности
- }
- }
- fin.close();
- for (int node = 0; node < number_of_nodes; ++node) { // Идем по всем бесцветым вершинам
- if (!color_of_painting[node]) {
- colorA = 0; // Обнуляем 2 счетчика для счета красных и черных вершин
- colorB = 0;
- painting(matrix, color_of_painting, node, 1); // Идем по всему дереву увеличивая счетчики
- if (colorA < colorB) { // Берем минимум на каждом этапе и увеличиваем сумму
- sum += colorA;
- } else {
- sum += colorB;
- }
- }
- }
- std::cout << sum << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement