CFR 664 D. Graph Coloring ( Adhoc )

Problem - D - Codeforces
It's clear that if the final colour is determined, and some vertex u has decided whether to flip or not, all the other vertices that are of the same component of u will decide itself whether should be flipped or not. Note that there might be many components, so we will have to first loop for the two possible colours, than for each component decide whether some determined vertex x should be flipped or not.
The concept is easy, but I got TLE for my original implementation. I used memcpy() to work around with the component vis[ ] array. It is a linear complexity function, so if there were N components, it will run for O( N ^ 2 ). I was not able to come up with any other cleaner implementation, so I decided to use VISFLAG, where -1 will do for the first check -- no flip, and then get it into the usual 1 for the second check -- do flip.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
typedef pair< int, int > pii; // v, color

int n, m;
vector< pii > G[ MAXN ];
int vis[ MAXN ];

int VISFLAG;

bool dfs( int u, int fa, int f, int gc, set< int > &flip ){
    vis[ u ] = VISFLAG;
    if( f ) flip.insert( u );
    for( pii p : G[ u ] ){
        int v = p.first;
        int c = p.second;
        if( c ^ f ^ flip.count( v ) == gc ){ // it's OK! Don't flip v
            if( vis[ v ] == VISFLAG ) continue; // GOOD^3
            if( !dfs( v, u, 0, gc, flip ) ) return false; // Can't satisfy without flipping the other end
        } else{ // has to flip v
            if( vis[ v ] == VISFLAG ) return false; // but it is visited -> must not be flipped
            if( !dfs( v, u, 1, gc, flip ) ) return false;
        }
    }
    return true;
}

void solve(){
    int ans = MAXN; // MAXN > 1e5 -> INF
    set< int > ans_chose;
    for( int col = 0; col < 2; ++col ){
        if( col == 1 ) memset( vis, 0, sizeof( vis ) );
        int sumcost = 0;
        set< int > chose;
        for( int root = 1; root <= n; ++root ) if( !vis[ root ] ){
            int ncost, ycost;
            set< int > nflip, yflip;
            VISFLAG = -1; // now see -1 as visited, others as unvisited
            if( dfs( root, -1, 0, col, nflip ) ){
                ncost = nflip.size();
            } else{
                ncost = MAXN;
            }
            VISFLAG = 1; // now see 1 as visited, otherwise not
            if( dfs( root, -1, 1, col, yflip ) ){
                ycost = yflip.size();
            } else{
                ycost = MAXN;
            }
            if( ncost == MAXN && ycost == MAXN ){
                sumcost = MAXN;
                break;
            }
            if( ncost < ycost ){
                sumcost += ncost;
                if( chose.size() < nflip.size() ) swap( chose, nflip ); // smaller to larger
                for( int u : nflip ) chose.insert( u ); // but won't be fast too much
            } else{
                sumcost += ycost;
                if( chose.size() < yflip.size() ) swap( chose, yflip );
                for( int u : yflip ) chose.insert( u );
            }
        }
        if( sumcost < ans ){
            ans = sumcost;
            swap( ans_chose, chose );
        }
    }
    if( ans == MAXN ) return ( void )puts("-1");
    printf("%d\n", ans);
    for( auto it = ans_chose.begin(); it != ans_chose.end(); ++it ){
        if( it != ans_chose.begin() ) putchar( ' ' );
        printf("%d", *it);
    }
    puts("");
}

int main(){
    scanf("%d%d", &n, &m);
    for( int i = 0; i < m; ++i ){
        int u, v;
        char s[ 2 ];
        scanf("%d%d", &u, &v);
        scanf("%s", s);
        int c = s[ 0 ] == 'R';
        G[ u ].push_back( pii( v, c ) );
        G[ v ].push_back( pii( u, c ) );
    }
    solve();
    return 0;
}