#include <stdio.
h>
#include <stdbool.h>
// Function to print the solution
void printSolution(int x[], int n) {
printf("Solution exists: Following are the assigned colors:\n");
for (int i = 0; i < n; i++)
printf(" %d ", x[i]);
printf("\n");
}
// Function to check if the current color assignment is safe for vertex v
bool isSafe(int v, int G[][10], int x[], int c, int n) {
for (int i = 0; i < n; i++) {
if (G[v][i] && c == x[i])
return false;
}
return true;
}
// A utility function to solve m Coloring problem
bool graphColoringUtil(int G[][10], int m, int x[], int k, int n) {
if (k == n) {
printSolution(x, n);
return true;
}
for (int c = 1; c <= m; c++) {
if (isSafe(k, G, x, c, n)) {
x[k] = c;
if (graphColoringUtil(G, m, x, k + 1, n))
return true;
x[k] = 0;
}
}
return false;
}
// Main function to solve the m Coloring problem
bool graphColoring(int G[][10], int m, int n) {
int x[10];
for (int i = 0; i < n; i++)
x[i] = 0;
if (!graphColoringUtil(G, m, x, 0, n)) {
printf("Solution does not exist");
return false;
}
return true;
}
int main() {
int n, m;
// Take the number of vertices and colors as input
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the number of colors: ");
scanf("%d", &m);
int G[10][10];
// Take the adjacency matrix as input
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &G[i][j]);
}
}
// Call the graphColoring function
graphColoring(G, m, n);
return 0;
}
