Construir un gráfico monocromático que encaja los nodos de los bordes -- ++ campo con performance camp codereview Relacionados El problema

Construct a monochromatic graph flipping nodes of the edges


1
vote

problema

Español

Dada una letra (A o B) que representa el color para n nodos de un gráfico y el conjunto de madores. ¿Es posible hacer que toda la gráfica tenga la letra A al voltear los nodos conectados por un borde?

Ejemplo:

Dado el siguiente gráfico de letras:
A - B

es imposible de hacer todas las letras a al voltear los nodos conectados por un borde.

con este gráfico es posible hacerlo (simplemente gire el segundo borde):
A - B - B

Para resolver este problema, he probado la fuerza bruta. Para cada borde, el programa realiza dos rutas (flip el borde i o no flip). He intentado memorizar algunos caminos que fueron visitados en la búsqueda para hacerlo más más rápido.

Descripción de la entrada:

Habrá varios casos de prueba. Cada caja de prueba comienza con dos enteros: n (1 ≤ n ≤ 1000) y m (1 ≤ m ≤ 4000). La siguiente línea contiene N letras, indicando la letra inicial de cada nodo. Luego sigue las líneas M, cada una con dos enteros, A y B (1 ≤ A, B ≤ N y A! = B), describiendo que hay un borde de A a b. Entrada termina con EOF.

Descripción de la salida:

Para cada caso de prueba, debe emitir y si es posible cumplir con los requisitos o n de lo contrario.

arriba de la entrada de ejemplo:

 2 1 A b 1 2 3 2 A b b 1 2 2 3 

SALIDA ANTERIOR DE EJEMPLO:

 norte Y 
  #include <cstdio> #include <vector> #include <utility> #include <unordered_map> #include <algorithm>  #define A 0 #define B 1  using edge = std::pair<int, int>;  std::unordered_map<unsigned int , int > visited_state; std::vector<edge> edge_list; std::vector<char> node_letters;  bool circuit;  bool isAllA(){     for (int i = 0; i < node_letters.size(); ++i)         if(node_letters[i] == B)             return false;     return true; }  //flip the color of the nodes in the eth edge void flipColors( int e ){     int u = edge_list[e].first;     int w = edge_list[e].second;      node_letters[u] = !node_letters[u];     node_letters[w] = !node_letters[w]; }   unsigned int getHashState(){     unsigned int hash1 = 63689 , hash2 = 378551;     unsigned int hash_state = 0;      for (int i = 0; i < node_letters.size(); ++i){         hash_state = hash_state * hash1 + node_letters[i];         hash1 *= hash2;     }      return hash_state; }    void brute_search( int i ){      //if its possible ends the recursion     if ( circuit )         return;       unsigned int hash = getHashState();      if (  visited_state[ hash ] ) {          //this state was visited on higher depth (dont need to search again)         if ( visited_state[ hash ] >= i + 1){             //puts("test repeated problems");             return;         }      }      visited_state[ hash ] = i + 1;      if(i == edge_list.size() ){         circuit = isAllA();         return;     }      //search without change the nodes on the ith edge     brute_search(i + 1);      //test with the changes     flipColors(i);     brute_search(i + 1);     flipColors(i);  }  int main ( void ){     int n,m;      while( scanf("%d %d ",&n,&m) != EOF ) {          //init and reset global variables         circuit = false;         node_letters.clear();         edge_list.clear();         visited_state.clear();          //read the letter of each node         for ( int i = 0 ; i < n ; ++i ) {             node_letters.push_back(getchar() - 'A');             getchar();//remove space             //printf("%d ",c[i]);         }          //read the edges         for (int i = 0; i < m; ++i) {             int u,w;             scanf("%d %d",&u,&w);             edge_list.push_back(edge(u - 1,w - 1));             //printf("%d %d ",v[i].first,v[i].second);         }           brute_search(0);          putchar(circuit ? 'Y' : 'N');         putchar(' ');     } }   
Original en ingles

Given a letter (A or B) representing the color for N nodes of a graph and the set of M edges. Its possible to make all the graph have the letter A by flipping the nodes connected by an edge ?

Example:

Given the following letter graph:
A - B

Its impossible to make all the letters A by flipping the nodes connected by some edge.

With this graph is possible to make it (Just flip the second edge ):
A - B - B

To solve this problem i've tried brute force. For every edge the program make two paths (flip the ith edge or not flip). I've tried to memoize some paths that was visited in the search to make it more faster.

Description of the input:

There will be several test cases. Each test case begins with two integers: N (1 xe2x89xa4 N xe2x89xa4 1000) and M (1 xe2x89xa4 M xe2x89xa4 4000). The next line contains N letters, indicating the starting letter of each node. Then follows M lines, each with two integers, a and b (1 xe2x89xa4 a,b xe2x89xa4 N and a != b), describing that there is an edge from a to b. Input ends with EOF.

Description of the output:

For each test case you should output Y if it is possible to meet the requirements or N otherwise.

Above example input:

 2 1 A B 1 2 3 2 A B B 1 2 2 3 

Above example output:

 N Y 
#include <cstdio> #include <vector> #include <utility> #include <unordered_map> #include <algorithm>  #define A 0 #define B 1  using edge = std::pair<int, int>;  std::unordered_map<unsigned int , int > visited_state; std::vector<edge> edge_list; std::vector<char> node_letters;  bool circuit;  bool isAllA(){     for (int i = 0; i < node_letters.size(); ++i)         if(node_letters[i] == B)             return false;     return true; }  //flip the color of the nodes in the eth edge void flipColors( int e ){     int u = edge_list[e].first;     int w = edge_list[e].second;      node_letters[u] = !node_letters[u];     node_letters[w] = !node_letters[w]; }   unsigned int getHashState(){     unsigned int hash1 = 63689 , hash2 = 378551;     unsigned int hash_state = 0;      for (int i = 0; i < node_letters.size(); ++i){         hash_state = hash_state * hash1 + node_letters[i];         hash1 *= hash2;     }      return hash_state; }    void brute_search( int i ){      //if its possible ends the recursion     if ( circuit )         return;       unsigned int hash = getHashState();      if (  visited_state[ hash ] ) {          //this state was visited on higher depth (dont need to search again)         if ( visited_state[ hash ] >= i + 1){             //puts("test repeated problems");             return;         }      }      visited_state[ hash ] = i + 1;      if(i == edge_list.size() ){         circuit = isAllA();         return;     }      //search without change the nodes on the ith edge     brute_search(i + 1);      //test with the changes     flipColors(i);     brute_search(i + 1);     flipColors(i);  }  int main ( void ){     int n,m;      while( scanf("%d %d ",&n,&m) != EOF ) {          //init and reset global variables         circuit = false;         node_letters.clear();         edge_list.clear();         visited_state.clear();          //read the letter of each node         for ( int i = 0 ; i < n ; ++i ) {             node_letters.push_back(getchar() - 'A');             getchar();//remove space             //printf("%d\n",c[i]);         }          //read the edges         for (int i = 0; i < m; ++i) {             int u,w;             scanf("%d %d",&u,&w);             edge_list.push_back(edge(u - 1,w - 1));             //printf("%d %d\n",v[i].first,v[i].second);         }           brute_search(0);          putchar(circuit ? 'Y' : 'N');         putchar('\n');     } } 
     

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

Esta no es una revisión, pero un comentario demasiado tiempo para ser un comentario.

La fuerza bruta casi siempre está mal. En las tareas como esta siempre está mal.

Deja que el gráfico tenga a Nodos coloreed A b8 Nodos Colored B .

Primer Aviso que voltear un borde no cambia la paridad de ni undefined0 Ni 99887776655443311 . A partir de esto, sigue inmediatamente que el IF ambos 99887766555443312 99887766555443313 son impares, el gráfico no se puede hacer monocromático.

Es un poco más difícil probar lo contrario, es decir, si al menos uno de undefined4 undefined5 es incluso, un gráfico conectado Se puede hacer monocromático. Demuestre que dados dos vértices de un color dado hay una secuencia de undefined6 se vuelve para que dos vértices de un color dado se vuelvan adyacentes. Luego usa la inducción.

Summing Up, la solución es identificar los componentes conectados del gráfico, y para cada uno de ellos contar las paridades del color.

 

This is not a review, but a comment too long to be a comment.

Brute force is almost always wrong. In the tasks like this it is always wrong.

Let the graph has a nodes colored A, and b nodes colored B.

First notice that flipping an edge doesn't change the parity of neither a nor b. From this, it follows immediately that the if both a and b are odd, the graph cannot be made monochromatic.

It is a bit harder to prove the opposite, that is if at least one of a and b is even, a connected graph can be made monochromatic. Prove that given two vertices of a given color there is a sequence of A-B flips so that two vertices of a given color become adjacent. Then use induction.

Summing up, the solution is to identify the connected components of the graph, and for each of them count the color's parities.

 
 

Relacionados problema

3  Generador de imágenes de Mandelbrot con iteración paralela  ( Mandelbrot image generator with parallel iteration ) 
Actualmente estoy tratando de optimizar esta clase que tengo para la generación fractal. La ecuación está destinada a ser conectable; He usado z => z*z + c ...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...

5  Memoria / Performance of Merge Sort Code  ( Memory performance of merge sort code ) 
Escribí un código de tipo de combinación para un poco de bocadillo nocturno. Lo he puesto trabajando, pero solo estaba mirando a aprender si me faltaba algo e...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

2  IMACROS BOT para realizar refrescos  ( Imacros bot for performing refreshes ) 
Estoy tratando de simplificar este código. Parece que todo funciona como debería; Sin embargo, cuando en el bucle de actualización de Imacro, parece un poco i...

6  Palindrome más largo en una matriz  ( Longest palindrome in an array ) 
Soy nuevo en la programación, y creo que este código podría mejorarse. ¿Alguna sugerencia? 'done'0 ...

4  Simulación simple de red neural en C ++ (Ronda 2)  ( Simple neural network simulation in c round 2 ) 
Intro Ayer He publicado esta pregunta . Desde entonces, he actualizado mi código para incorporar estas sugerencias . También he eliminado la dependencia d...

5  Encuentre el próximo número Prime - Control de flujo de los bucles anidados 'para `  ( Find the next prime number flow control of nested for loops ) 
Este código funciona perfectamente, pero me molesta. Tener un bucle etiquetado y anidado Bucle, con un Enumerable<T>.Empty()0 Declaración, y un 9988777665...

1  Integración de oscilador de fase perturbada  ( Perturbed phase oscillator integration ) 
Estoy integrando un sistema de osciladores de fase perturbados. Defino el sistema de ecuación y también la matriz jacobiana. Tengo que remodelar el vector dim...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos