Gráfico algoritmo para colorear: típico problema de programación

Question

Estoy entrenando problemas de código como UVA y tengo éste en el que que hacerlo, dado un conjunto de n exámenes y k estudiantes matriculados en los exámenes, si encuentra es posible programar todos los exámenes en dos intervalos de tiempo.

entrada varios casos de prueba. Cada uno comienza con una línea que contiene n de diferentes exámenes para programar. La 2da línea tiene el número de casos k en los cuales existen al menos 1 estudiante matriculado en 2 exámenes. Luego, seguirán las líneas k, cada una con 2 números que especifican el par de exámenes para cada caso anterior. (Una entrada con n = 0 significa el final de la entrada y no debe procesarse).

Salida: Usted tiene que decidir si el plan de inspección es posible o no para 2 ranuras de tiempo.

Ejemplo:

de entrada:

3 
3 
0 1 
1 2 
2 0 
9 
8 
0 1 
0 2 
0 3 
0 4 
0 5 
0 6 
0 7 
0 8 
0 

salida de la señal:

NOT POSSIBLE. 
POSSIBLE. 

creo que el enfoque general es coloreado de grafos, pero yo soy un Novato y puedo confesar que Tuve algunos problemas para entender el problema. De todos modos, estoy tratando de hacerlo y luego enviarlo. ¿Podría alguien ayudarme a hacer algo de código para este problema? Tendré que manejar y entender este algo ahora para usarlo más adelante, una y otra vez.

prefiero C o C++, pero si lo desea, Java está bien para mí;)

Gracias de antemano

Answer 1

He traducido el pseudocódigo del polygenelubricant al código JAVA, para proporcionar una solución a mi problema. Tenemos una plataforma de envío (como concursos uva/ACM), por lo que sé que pasó incluso en el problema con más casos y más difíciles.

Aquí está:

import java.util.ArrayList; 
import java.util.Hashtable; 
import java.util.Scanner; 

/** 
* 
* @author newba 
*/ 
public class GraphProblem { 

    class Edge { 
     int v1; 
     int v2; 

     public Edge(int v1, int v2) { 
      this.v1 = v1; 
      this.v2 = v2; 
     } 
    } 

    public GraphProblem() { 
     Scanner cin = new Scanner(System.in); 

     while (cin.hasNext()) { 

      int num_exams = cin.nextInt(); 
      if (num_exams == 0) 
       break; 
      int k = cin.nextInt(); 
      Hashtable<Integer,String> exams = new Hashtable<Integer, String>(); 
      ArrayList<Edge> edges = new ArrayList<Edge>(); 
      for (int i = 0; i < k; i++) { 
       int v1 = cin.nextInt(); 
       int v2 = cin.nextInt(); 
       exams.put(v1,"UNKNOWN"); 
       exams.put(v2,"UNKNOWN"); 
       //add the edge from A->B and B->A 
       edges.add(new Edge(v1, v2)); 
       edges.add(new Edge(v2, v1)); 
      } 

      boolean possible = true; 
      for (Integer key: exams.keySet()){ 
       if (exams.get(key).equals("UNKNOWN")){ 
        if (!colorify(edges, exams,key, "BLACK", "WHITE")){ 
         possible = false; 
         break; 
        } 
       } 
      } 

      if (possible) 
       System.out.println("POSSIBLE."); 
      else 
       System.out.println("NOT POSSIBLE."); 

     } 
    } 

    public boolean colorify (ArrayList<Edge> edges,Hashtable<Integer,String> verticesHash,Integer node, String color1, String color2){ 

     verticesHash.put(node,color1); 
     for (Edge edge : edges){ 
      if (edge.v1 == (int) node) { 
       if (verticesHash.get(edge.v2).equals(color1)){ 
        return false; 
       } 
       if (verticesHash.get(edge.v2).equals("UNKNOWN")){ 
        colorify(edges, verticesHash, edge.v2, color2, color1); 
       } 
      } 
     } 
     return true; 
    } 

    public static void main(String[] args) { 
     new GraphProblem(); 
    } 
} 

yo no optimizado, sin embargo, no tengo el tiempo justo nuevo, pero si lo desea,/podemos discutir aquí.

Espero que lo disfrutes! ;)

Answer 2

Tiene razón en que este es un problema de coloreado de grafos. Específicamente, debe determinar si el gráfico es 2-colorable. Esto es trivial: haga un DFS en el gráfico, coloreando nodos en blanco y negro alternativos. Si encuentras un conflicto, entonces el gráfico no es 2-colorable, y la programación es imposible.

possible = true 

for all vertex V 
    color[V] = UNKNOWN 

for all vertex V 
    if color[V] == UNKNOWN 
    colorify(V, BLACK, WHITE) 

procedure colorify(V, C1, C2) 
    color[V] = C1 
    for all edge (V, V2) 
    if color[V2] == C1 
     possible = false 
    if color[V2] == UNKNOWN 
     colorify(V2, C2, C1) 

Esto se ejecuta en O(|V| + |E|) con la lista de adyacencia.

Answer 3

en la práctica, la pregunta es si puede dividir los n exámenes en dos subconjuntos A y B (dos intervalos de tiempo) de modo que para cada par en la lista de k pares de exámenes, uno pertenece a A y b pertenece a B, o un pertenece a B y B pertenece a A.

Tiene usted razón de que se trata de un problema de 2 colores; es un gráfico con n vértices y hay un arco no dirigido entre los vértices a y b si el par o aparece en la lista. Luego, la pregunta es acerca de la 2-colorabilidad del gráfico, los dos colores que denotan la partición en los intervalos de tiempo A y B.

Un gráfico de 2 colores es un "gráfico bipartito". Puede probar bipartitos fácilmente, vea http://en.wikipedia.org/wiki/Bipartite_graph.