# Construct a monochromatic graph flipping nodes of the edges

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 ≤ N ≤ 1000) and M (1 ≤ M ≤ 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 ≤ a,b ≤ 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]);
}

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');
}
}


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.