import Prog1Tools.IOTools;
public class FaerRaDue{  
 //
 //
 // Es wird eine optimale, d. h. mit
 // den wenigst moeglichen Farben, 
 // eines Graphen konstruiert. 
 //
 static int voropt ;  // Hier ist das vorlaeufige Optimum vermerkt. 
 //
 //   Zunaechst die Eingabeprozedur. 
 //
 //
  //
 public static void Einlesen(int[][] graph, double c, int n){ // Eingabe ist die Anzahl der Knoten. 
                                                             //  Produktion der Adjazenzmatrix des Graphen. 
 int anz = 0;//
 //
 //
 for (int i = 0; i < n; i++) {  // i geht die Zeilen lang. 
    //
    for (int j = i; j < n; j++) { // j geht die Spalten lang. 
    //     
    if (i == j) {
    graph[i][i] = 0;
    continue; }
    //
    if (Math.random()* n  <= c) {
    graph[i][j] = 1; 
    anz = anz +1;}
    //
    graph[j][i] = graph[i][j];
    }
   }
    System.out.println("Anzahl Kanten ist  " + anz);
 }
 //
 //
 //
 //  Der Loesungsraum ist die Menge aller
 //  Abbildungen F: {0,.. n-1} --> {0,1, ..., n-1}
 //  die jedem Knoten eine Farbe zuordnen. Nach Vorueberlegung
 //  reicht es, fuer Knoten i die Farben 0,1,2,3, ..., nur bis i
 //  auszuprobieren.
 //
 //
public static void Faerb(int[][] graph,  int[] F , 
                         int[] Fvoropt,  int knoten) {  
                                    // 
				    // Eine optimale Faerbung von graph. 
                                    // F die partielle Faerbung,
                                    // knoten der Knoten, der dran ist,
                                    // anz Anzahl der verbrauchten Farben. 
                                    //
int anz = 0;     //Hier wird die Anzahl der Farben in F ermittelt.  
                 // 
int[] Test = new int[F.length];
//
for (int i = 0; i < knoten; i++) Test[F[i]] = 1;
//
//
for (int i = 0; i < knoten; i++) if (Test[i] > 0) anz = anz + 1;      //
                                                                      //
								      //
                         //
//
// 
if (knoten == F.length && anz < voropt)  { // Eine neue Faerbung. 
    voropt = anz; 
    for (int  i = 0; i < F.length; i++)		  
	Fvoropt[i] = F[i]; 
	return; 
	}		  
//
if (anz >= voropt) return;    // Es hat sowieso keinen Sinn mehr weiterzumachen.  
//			  
naeFar: for (int i = 0; i <= knoten; i++) { //Testen die Farben 0,1,2,...knoten.
         // 
	  for (int j = 0; j < knoten ; j++)  { // Gucken, ob Farbe passt. 
            if (graph[knoten][j] == 1 && F[j] == i) continue naeFar; }
            //
	    F[knoten] = i; 
	    Faerb(graph, F, Fvoropt, knoten + 1); 
	    //
	    }                                  
 }
 //
 //
 //
 public static void Ausgabe(int[ ] F, int voropt) {
 int i = 0;
 while (i < F.length) {
    System.out.println("Farbe von  " + i + " ist " +  F[i]);
    i++; 
    }     
 System.out.println("Anzahl von Farben ist" + voropt);
 }     
  //
  
  //
  //
  public static void main(String[] args) {
  //
  int groesse; 
  double c; 
  int[] F, Fvoropt;
  int[][] graph;
  //  
  //
  groesse = IOTools.readInteger("groesse einlesen " );
  //
  voropt = groesse + 1; // Das "+1+" ist wichtig, damit sich am Anfang was tut. 
  //
  graph = new int[groesse][groesse];
  //
  c = IOTools.readDouble("Duennes c einlesen " );
  //
  Einlesen( graph, c,  groesse);
  //
  F= new int[groesse];
  //
  Fvoropt = new int[groesse];
  // 
  Faerb(graph, F, Fvoropt, 0);
  
  Ausgabe(Fvoropt, voropt); 
    } 
  }