1
\$\begingroup\$

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

        //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');
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.