[sotong] R3 4-color graph coloring

/* 4 color graph coloring */
/*
output:
108
96
264

input:
3
4
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
5
0 1 1 1 0
1 0 0 1 1
1 0 0 1 0
1 1 1 0 1
0 1 0 1 0
7
0 1 0 0 1 0 1
1 0 1 0 1 0 0
0 1 0 1 1 0 0
0 0 1 0 1 1 0
1 1 1 1 0 1 1
0 0 0 1 1 0 1
1 0 0 0 1 1 0
*/
#include "stdafx.h"

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <assert.h>

using namespace std;

class algorithm
{
public:
    void solution(char *input, char *output);
};

typedef std::set<int> set_t;
typedef std::map<int, set_t> graph_t;
typedef std::map<int, int> colormap_t;

graph_t G;
set_t V; // visited
colormap_t colormap;

typedef unsigned char color_t;
const color_t COLOR1 = (0x1 << 0);
const color_t COLOR2 = (0x1 << 1);
const color_t COLOR3 = (0x1 << 2);
const color_t COLOR4 = (0x1 << 3);
const color_t ALL_COLORS = (COLOR1 | COLOR2 | COLOR3 | COLOR4);

int solve(int begin_vertex, int sofar = 1)
{
    set_t::iterator Vit = V.find(begin_vertex);

    if(V.end() != Vit) { return 0; }

    graph_t::iterator g = G.find(begin_vertex);
    if( g == G.end() || g->second.empty() ) { return 0; }

    V.insert(begin_vertex);

    set_t & adj_set = g->second;

    color_t adj_colors = 0;

    std::vector<int> tovisit;
    set_t::iterator adj_it = adj_set.begin();
    for(; adj_it != adj_set.end(); ++adj_it)
    {
        const int adj_vertex = *adj_it;
        if(V.find(adj_vertex) != V.end())
        {
            assert(colormap.find(adj_vertex) != colormap.end());
            adj_colors |= colormap[adj_vertex];
        }
        else
        {
            tovisit.push_back(adj_vertex);
        }
    }

    const size_t num_tovisit = tovisit.size();

    int ret = 0;
    if(num_tovisit == 0)
    {
        ret += !(adj_colors & COLOR1);
        ret += !(adj_colors & COLOR2);
        ret += !(adj_colors & COLOR3);
        ret += !(adj_colors & COLOR4);
    }
    else
    {
        for(int color = 0; color < 4; ++color)
        {
            const int colorbit = 0x1 << color;

            // used color
            if(adj_colors & colorbit) { continue; }

            colormap[begin_vertex] = colorbit;

            for(size_t v = 0; v < num_tovisit; ++v)
            {
                ret += solve(tovisit[v], 1);
            }
        }
    }
    Vit = V.find(begin_vertex);
    assert(Vit != V.end());
    V.erase(Vit);
    return ret;
}

void algorithm::solution(char *input, char *output)
{

    ifstream infile(input);
    ofstream outfile;
    outfile.open(output);

    int T;
    infile >> T;

    for (int t = 1; t <= T; t++)
    {
        size_t N;
        infile >> N;

        G.clear();

        for(size_t r = 0; r < N; ++r)
        {
            for(size_t c = 0; c < N; ++c)
            {
                int v;
                infile >> v;
                if(v == 1)
                {
                    G[r].insert(c);
                    G[c].insert(r);
                }
            }
        }
        if(!G.empty())
        {
            int begin = G.begin()->first;
            int S = solve(begin);
            outfile << S << '\n';
        }
        else
        {
            outfile << 0 << '\n';
        }

    }
}
#if 1
int main(int argc, char * argv[])
{
    algorithm().solution("input.txt", "output.txt");
    return 0;
}
#endif