mcoloring.cpp

来自「回溯法的m着色问题」· C++ 代码 · 共 62 行

#define N 10
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

bool G[N][N];
int n,m,x[N];

int nextvalue(int k)
{
	for(;;)
	{
		x[k]=x[k]+1;
		if (x[k]==m+1){
			x[k]=0;
			return x[k];
		}
		for(int j=1;j<=n;j++)
			if (G[k][j]&&x[k]==x[j])
				break;
		if (j==n+1)
			return 0;
	}
}

void mcoloring(int k)
{
	
	for(int i=1;i<=m;i++)
	{
		nextvalue(k);
		if (x[k]==0)
			break;
		if (k==n)
		{	for(int j=1;j<=n;j++)
				printf("%d",x[j]);
			printf("\n");
		}	
		else
			mcoloring(k+1);
	}
}

int main()
{
	printf("input n(着色点数)=? ");
	scanf("%d",&n);
	printf("input m(最大色数)=? ");
	scanf("%d",&m);
	printf("input G[][]=?\n");
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{	
			printf("G[%d][%d]=",i,j);
			scanf("%d",&G[i][j]);
		}
	for(i=1;i<=n;i++)
		x[i]=0;
	mcoloring(1);
	return 0;
}