図シェーディング問題配色案C++実現遡及法

1596 ワード

/*      :        
 *        :    
 *        :2015 5 21   12:02:00.000
 *      :Dev-C++ 5.8.3
 */
#include
#include
using namespace std;
int n,m,g,i;  //n          ,m      ,g         
int a[10000][10000];  //        10000   
void NextValue(int k,int m,int* x); 
void mColoring(int k,int m,int *x);
void mColoring(int m,int *x);

int main()      //   
{
	memset(a,0,sizeof(a)); 
	cout << "            : ";
	cin >> n;
	cout << "       : ";
	cin >> g;
	cout << "       : "; 
	cin >> m;
	int *x = new int[100];
    int u, v;
    for(i = 0; i < n; i++) x[i] = 0;
    for(i = 0; i < g; i++)
	{
		cout << "    :";
		cin >> u >> v;
	    a[u][v] = a[v][u] = 1;
	}
	cout << "    : " << endl; 
	mColoring(m,x);

    return 0;
}

void NextValue(int k,int m,int* x)
{
	//    [1,m]  x[k]        ,            
	//x[k]=0         ,   1      
	int j;
    do{
		x[k]=(x[k]+1) % (m+1);    		 //        
		if(!x[k]) return;         		 //       
		for(j = 0; j < k; j++)  {
			if(a[k][j] && x[k] == x[j])  // (i,j)    ,     k j     
				break;                   //    ,        
			}
		if(j == k) return;               //           
	}while(1);
}
void mColoring(int k,int m,int *x)
{
	do{
		NextValue(k, m, x);             // x[k]     
		if(!x[k])  break;               //x[k]=0            
		if(k == n - 1) {                //   G   m-     
			for(int i = 0; i < n; i++)  cout<