#include <stdio.h>
#include <string.h>

public class ColorearGrafo {

  /**
   * Colorea todos los vertices del grafo usando la técnica de Voraces.
   *
   * @param matrizAdj int[][] - La matriz de adyacencia define las conexiones de
   * vertices en el grafo.
   *
   * @param vertices List - Lista con los vertices del grafo.
   *
   * @return int - Retorna el número de colores usados.
   */
  public static int colorGrafo(int[][] matrizAdj, List vertices) {

    int colorActual = 0;
    boolean esCompleto = false;

    /* do...mientras se colorean todos los nodos */
    do {

      /* Se incrementa para obtener el siguiente color que no ha sido usado */
      colorActual++;

      /* Pintamos todos los nodos posibles del mismo color */
      coloreadoConUnColorVoraz(matrizAdj, vertices, colorActual);

      /* Mira si hay algún nodo a la izquierda no coloreado */
      esCompleto = true; // Se asume que no hay nodos sin colorear

        //Comprueba que no haya ningun vértice con color = 0, si lo hay
        //sigue con otro color
      for (int i = 0; esCompleto && i < vertices.size(); i++) {
        //Cuando es el color = 0 sale del for y continua con otro color
        //ya que hay aún algún vértice sin colorear
        esCompleto = (((Vertice) vertices.get(i)).getNumeroColor() != 0);
      }

    }
    while (!esCompleto);

    /* Retornamos el número de colores usados */
    return colorActual;
  }

  /**
   * Coloreamos de un mismo color tantos vértices del grafo como sean posibles,
   * usando la técnica de voraces.
   *
   * @param matrizAdj int[][] - La matriz de adyacencia define las conexiones de
   * vertices en el grafo.
   *
   * @param vertices List - Lista con los vertices del grafo.
   *
   * @param numeroColor int - El color con el cual coloreamos los vertices al
   * llamar a este método.(Varia según se vayan usando los colores).
   *
   * @return List - Retorna la lista de los nuevos vértices coloreados.
   */
  private static List coloreadoConUnColorVoraz(int[][] matrizAdj,
                                               List vertices,
                                               int numeroColor) {

    List verticesColoreados = new ArrayList();

    /* Encontramos el primer vértice sin colorear */
    Vertice v = null;
    for (int i = 0; v == null && i < vertices.size(); i++) {
      if ( ( (Vertice) vertices.get(i)).getNumeroColor() == 0) {
        v = (Vertice) vertices.get(i);
      }
    }
    /*Pintamos todos los vértices que no sean adyacentes*/
    while (v != null) {
      /* Miramos si el vértice v es adyacente con otros vértices en el color actual*/
      boolean adyacente = false;

      for (int i = 0; !adyacente && i < verticesColoreados.size(); i++) {
        //Comprueba si alguno de los ya coloreados con adyacentes para no pintarlo
        adyacente = !sonAdyacentes(matrizAdj, (Vertice) verticesColoreados.get(i), v);
      }
      /* Si no es adyacente con otros vértices, coloreamos el vértice v
         y lo añadimos a la lista de coloreados*/
      if (!adyacente) {
        v.setNumeroColor(numeroColor);
        verticesColoreados.add(v);
      }

      /* Encontrar el siguiente vértice sin colorear */
      int inicioIndice = vertices.indexOf(v);
      v = null;
      for (int i = inicioIndice + 1; v == null && i < vertices.size(); i++) {
        if ( ( (Vertice) vertices.get(i)).getNumeroColor() == 0) {
          v = (Vertice) vertices.get(i);
        }
      }
    }
    return verticesColoreados;
  }


  /**
   * Comprueba si entre dos vertices pasados como parámetro hay conexión.
   *
   * @param matrizAdj int[][] - La matriz de adyacencia define las conexiones de
   * vertices en el grafo.
   *
   * @param v1 Vertice - El primer vértice.
   *
   * @param v2 Vertice - El segundo vértice.
   *
   * @return boolean - Retorna true si v1 y v2 están relacionados (o en la matrizAdj)
   * o false en caso contrario.
   */
  private static boolean sonAdyacentes(int[][] matrizAdj, Vertice v1,
                                        Vertice v2) {

    int id1 = v1.getIdentidad();
    int id2 = v2.getIdentidad();

    return matrizAdj[id1][id2] == 0;
  }

}

int main(){


return 0;

}