3-coloring problem

#include <iostream> #include <vector> #include <Windows.h> using namespace std; bool isSafe(const vector<vector<int>> &graph, const vector<int> &color, int v, int c) { for (int i = 0; i != graph.size(); ++i) if (graph[v][i] == 1 && color[i] == c) return false; return true; } void printSolution(const vector<int> &color) { cout << "Solution exist: " << endl; for (auto a : color) cout << a << " "; } bool graphColoringUti(const vector<vector<int>> &graph, vector<int> &color, int v, int m) { if (v == graph.size()) return true; for (int c = 1; c <= m; ++c) { if (isSafe(graph, color, v, c)) { color[v] = c; if (graphColoringUti(graph, color, v + 1, m)) return true; // if assign color c does not lead to a solution, reset it color[v] = 0; } } return false; } bool graphColoring(const vector<vector<int>> &graph, int m) { vector<int> color(graph.size(), 0); if (!graphColoringUti(graph, color, 0, 3)) { cout << "Solution Not Exist"; return false; } printSolution(color); return true; } int main() { vector<vector<int>> graph = { { 0, 1, 1, 1 }, { 1, 0, 1, 0 }, { 1, 1, 0, 1 }, { 1, 0, 1, 0 }, }; int m = 3; graphColoring(graph, 3); cout << endl; system("PAUSE"); return 0; }