// 1.9.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "iostream"

#include "stdio.h"

using namespace std;

bool ColoringGraph(int G[][],int n,int m);

bool IsOk(int G[][],int color[],int k,int n) ;

int G[][]={{,,,,},{,,,,},{,,,,},{,,,,},{,,,,}};

int _tmain(int argc, _TCHAR* argv[])

{

    int n=,m=;

    ColoringGraph(G,n,m);

    return ;

}

bool ColoringGraph(int G[][],int n,int m)

    //n是图的定点个数，G是图的连接矩阵，Gij=1说明i定点与j定点有连接。m是最多可以上的色

    //若输出有效上色，返回1，否则返回0

{

    int *color=new int[n];

    for(int i=;i<n;i++)//给每个顶点颜色初始化为0

        color[i]=;

    int k=;

    while(k>=)//k代表顶点个数，当k回溯到0说明已经没有可行解了

    {

        while(color[k]<=m)

        {

            color[k]++;

            if (IsOk(G,color,k,n))

                break;

        }

        if(color[k]<=m && k==n-)

        {

            cout<<"OK";

            for(int j=;j<n;j++)

                cout<<color[j];

            return ;

        }

        else if(color[k]<=m && k<n-)

        {

            k++;

        }

        else//若k>m,说明此路不同回溯到上一层

        {

            color[k]=;

            k--;

        }

    }

    return ;

}

bool IsOk(int G[][],int color[],int k,int n)  //判断是否有相同色的顶点，与之是一个边的

{

    for(int i=;i<n;i++)

    {

        if(G[i][k]== && color[i]==color[k])

            return false;

    }

    return true;

}