Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int** vvodmatr(int n)
- {
- cout << "Введите вашу матрицу смежности: \n";
- int** matrix = new int* [n];
- for (int i = 0; i < n; i++)
- matrix[i] = new int[n];
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> matrix[i][j];
- return matrix;
- }
- bool isgood(int*col, int**matrix, int n)
- {
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- if (matrix[i][j] && (col[i] == col[j]) && (col[i] != 0))
- return false;
- return true;
- }
- bool color(int*col, int k, int n, int**matrix)
- {
- bool f = false;
- int i = 1;
- for (i; i >= 0 && i < n; i++)
- {
- ex:
- if (f)
- {
- f = false;
- if (col[i] > k)
- goto ex2;
- }
- else
- if (col[i] + 1 <= k)
- col[i]++;
- else
- goto ex2;
- ex1:
- if (!isgood(col,matrix,n))
- if (col[i] == k)
- {
- ex2:
- col[i] = 0;
- if (i - 1 >= 0)
- {
- col[i - 1]++;
- i--;
- }
- else
- return 1;
- f = true;
- goto ex;
- }
- else
- {
- col[i]++;
- goto ex1;
- }
- }
- if (i < 0)
- return true;
- return false;
- }
- void deletematrix(int** m, int n)
- {
- for (int i = 0; i < n; i++)
- delete[] m[i];
- delete[] m;
- }
- int main()
- {
- setlocale(LC_ALL, "RU");
- int n;
- cout << "Введите количество вершин: \n";
- cin >> n;
- int** matrix = vvodmatr(n);
- int* col = new int[n];
- for (int k = 4; k > 0; k--)
- {
- col[0] = 1;
- for (int l = 1; l < n; l++)
- col[l] = 0;
- if (color(col,k,n,matrix))
- {
- cout << "Хроматическое число = " << k + 1;
- break;
- }
- }
- deletematrix(matrix, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement