Advertisement
codisinmyvines

dsdsdsdsdasd

Nov 2nd, 2020
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int** vvodmatr(int n)
  5. {
  6.     cout << "Введите вашу матрицу смежности: \n";
  7.     int** matrix = new int* [n];
  8.     for (int i = 0; i < n; i++)
  9.         matrix[i] = new int[n];
  10.     for (int i = 0; i < n; i++)
  11.         for (int j = 0; j < n; j++)
  12.             cin >> matrix[i][j];
  13.     return matrix;
  14. }
  15. bool isgood(int*col, int**matrix, int n)
  16. {
  17.     for (int i = 0; i < n; i++)
  18.         for (int j = 0; j < n; j++)
  19.             if (matrix[i][j] && (col[i] == col[j]) && (col[i] != 0))
  20.                 return false;
  21.     return true;
  22. }
  23. bool color(int*col, int k, int n, int**matrix)
  24. {
  25.     bool f = false;
  26.     int i = 1;
  27.     for (i; i >= 0 && i < n; i++)
  28.     {
  29.     ex:
  30.         if (f)
  31.         {
  32.             f = false;
  33.             if (col[i] > k)
  34.                 goto ex2;
  35.         }
  36.         else
  37.             if (col[i] + 1 <= k)
  38.                 col[i]++;
  39.             else
  40.                 goto ex2;
  41.     ex1:
  42.         if (!isgood(col,matrix,n))
  43.             if (col[i] == k)
  44.             {
  45.             ex2:
  46.                 col[i] = 0;
  47.                 if (i - 1 >= 0)
  48.                 {
  49.                     col[i - 1]++;
  50.                     i--;
  51.                 }
  52.                 else
  53.                     return 1;
  54.                 f = true;
  55.                 goto ex;
  56.             }
  57.             else
  58.             {
  59.                 col[i]++;
  60.                 goto ex1;
  61.             }
  62.     }
  63.     if (i < 0)
  64.         return true;
  65.     return false;
  66. }
  67. void deletematrix(int** m, int n)
  68. {
  69.     for (int i = 0; i < n; i++)
  70.         delete[] m[i];
  71.     delete[] m;
  72. }
  73. int main()
  74. {  
  75.     setlocale(LC_ALL, "RU");
  76.     int n;
  77.     cout << "Введите количество вершин: \n";
  78.     cin >> n;
  79.     int** matrix = vvodmatr(n);
  80.     int* col = new int[n];
  81.     for (int k = 4; k > 0; k--)
  82.     {
  83.         col[0] = 1;
  84.         for (int l = 1; l < n; l++)
  85.             col[l] = 0;
  86.         if (color(col,k,n,matrix))
  87.         {
  88.             cout << "Хроматическое число = " << k + 1;
  89.             break;
  90.         }
  91.     }
  92.     deletematrix(matrix, n);
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement