Coloring

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

typedef long long ll;

const int N = 10;
const int M = 5;
const int START = 3;

int maxSize;

struct Component
{
    int p[N];
    int sz[N];
};

struct State
{
    Component c[M];
    int adj[N][N];
};

void init_component(Component* r)
{
    for(int i=0;i<N;i++)
    {
        r->p[i] = i;
        r->sz[i] = 1;
    }
}

void init_state(State* state)
{
    for(int i=0;i<M;i++)
        init_component(&state->c[i]);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            state->adj[i][j] = -1;
}

void component_merge(Component* comp, int a, int b)
{
    int ca = comp->p[a];
    int cb = comp->p[b];

    if( ca != cb )
    {
        for(int i=0;i<N;i++)
            if ( comp->p[i] == cb )
            {
                comp->sz[cb]--;
                comp->p[i] = ca;
                comp->sz[ca]++;
            }
    }

}

int stateCount;

bool solve(State state, int colorTop)
{
    stateCount++;
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            if ( state.c[i].sz[j] > maxSize )
                return false;

    bool changes = true;
    while(changes)
    {
        changes = false;
        for(int i=0;i<N;i++)
            for(int j=i+1;j<N;j++)
                for(int k=0;k<colorTop;k++)
                    if(state.c[k].p[i] == state.c[k].p[j] && state.adj[i][j] == -1)
                    {
                        state.adj[j][i] = state.adj[i][j] = k;
                        changes = true;
                    }
    }

    int best = -1;
    int bestI = -1, bestJ = -1;

    for(int i=0;i<N;i++)
        for(int j=i+1;j<N;j++)
            if(state.adj[i][j] == -1)
            {
                int ways = 0;
                for(int k=0;k<colorTop;k++)
                {
                    int iid = state.c[k].p[i];
                    int jid = state.c[k].p[j];

                    if(state.c[k].sz[iid] + state.c[k].sz[jid] <= maxSize)
                        ways++;
                }
                if( best == -1 || ways < best )
                {
                    best = ways;
                    bestI = i;
                    bestJ = j;
                }
            }

    if ( best == -1 )
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                printf("%d ", state.adj[i][j]);
            puts("");
        }

        for(int k = 0 ; k < M; k++)
        {
            int ecnt = 0;
            for(int i=0;i<N;i++)
                for(int j=i+1;j<N;j++)
                    if(state.adj[i][j] == k)
                        ecnt++;
            printf("%d %d\n", N, ecnt);
            for(int i=0;i<N;i++)
                for(int j=i+1;j<N;j++)
                    if(state.adj[i][j] == k)
                        printf("%d %d\n", i+1, j+1);
            puts("====");
        }

        return true;
    }

    for(int k=0;k<colorTop;k++)
    {
        State s2 = state;
        int i, j;
        i = bestI;
        j = bestJ;
        s2.adj[i][j] = s2.adj[j][i] = k;
        component_merge(&s2.c[k], i, j);

        if( solve( s2, ( k == colorTop-1 && colorTop < M ) ? colorTop+1 : colorTop ) )
            return true;

        s2.adj[i][j] = s2.adj[j][i] = -1;
    }

    return false;
}

int main()
{
    State state;
    init_state(&state);

    state.adj[0][1] = state.adj[0][2] = 0;
    component_merge(&state.c[0], 0, 1);
    component_merge(&state.c[0], 0, 2);

    for(maxSize = START; ; maxSize++)
    {
        stateCount = 0;
        printf("maxSize = %d\n", maxSize);
        if ( solve(state, 2) )
        {
            printf("size = %d\n", maxSize);
            break;
        }
        printf("State Count = %d\n", stateCount);
    }
}