#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

using namespace std;

const int n=35; // nombre de sommets
int adj[n][n];  // matrice d'adjacence du graphe
int couleur1[n];  // couleurs des sommets pour l'agorithme exact
bool trouve=false; // permet de stopper l'algorithme exact
                   // quand une coloration  a ete trouvee


bool convient(int x, int c) // teste si la couleur c peut être donnee au sommet x (elle n'est pas utilisee par un de ses voisins)
{
     for(int i=0;i<x;i++)
      if(adj[x][i] && (couleur1[i]==c)) return false;
     return true;
}



void colorRR(int x, int k) // fonction recursive pour tester toutes les couleurs possible pour le sommet x
{ 
     if(x==n)
     { cout << "Coloration en " << k << " couleurs trouvee" << endl;
       for(int i=0;i<n;i++) cout << "couleur de " << i << " : " << couleur1[i] << endl; 
       trouve=true;
     }
     else
     for(int c=1;c<=k;c++)
      if(convient(x,c)) 
	{couleur1[x]=c;
         colorRR(x+1,k);
	 if(trouve) return;}
}

void colorExact(int k) // teste si le graphe possede une coloration en k couleurs en essayant toutes les combinaisons
{
    for(int i=0;i<n;i++)
     couleur1[i]=0;
     colorRR(0,k);
     if(!trouve) cout << "Pas de coloration en " << k <<" couleurs" << endl;
}