図シェーディング問題配色案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<