图的着色问题 回溯法.txt

来自「包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题」· 文本 代码 · 共 70 行

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//图的着色问题 回溯法
/*
输入：
5 7 3
0 1
0 2
1 2
1 3
1 4
2 4
3 4

输出：
1
1 2 3 1 3
*/
int path[10][10]={0};
int color[10]={0};

bool isok(int yuan,int n)
{	//判断点的着色是否符合游戏规则
	int i;
	for(i=0;i<n;i++)
	{
		if(i!=yuan&&path[i][yuan]==1&&color[i]==color[yuan]) return false;
	}
	return true;
}

bool GColor(int n,int limit)
{
	int k=0;//做第k个点的着色
	while(k>=0)
	{
		color[k]=1;
		while(isok(k,n)==false&&color[k]<limit)
		{//当前颜色不符合游戏规则，换颜色
			color[k]++;
		}
		if(color[k]<=limit)
		{	//在规定的颜色数量内
			k++;//做下一个点的着色
			if(k>=n) return true;//所有的点都着上颜色
		}
		else  k--;//超过规定颜色数量，回溯
	}
	return false;
}

int main()
{
	int num,pathnum,tempa,tempb,i,limit;
	scanf("%d%d%d",&num,&pathnum,&limit);
	for(i=0;i<pathnum;i++)
	{
		scanf("%d%d",&tempa,&tempb);
		path[tempa][tempb]=path[tempb][tempa]=1;
	}
	printf("%d\n",GColor(num,limit));
	for(i=0;i<num;i++)
	{
		printf("%d ",color[i]);
	}
	return 0;
}