回溯法解决染色问题（递归版和迭代版）

染色问题：相邻的点不能染同样的颜色

如果使用递归版：一定要记得“恢复现场”！！！c[k]=0

如果使用递归版：一定要记得“恢复现场”！！！c[k]=0

如果使用递归版：一定要记得“恢复现场”！！！c[k]=0

建图使用的是Acwing的方法

由于建立的是无向图，一定要记得添加双向的边：

add(a,b),add(b,a)

测试数据：

5 7
1 2
1 3
2 4
2 5
3 4
3 5
4 5

#include<iostream>
#include<cstring>
using namespace std;
const int N=100;
int c[N];
int n,m,idx;
int e[N],ne[N],h[N];
bool flag=false;
/*
5 7
1 2
1 3
2 4
2 5
3 4
3 5
4 5
*/
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void graphcolor(int k)
{
	for(int i=1;i<=3;i++)
	{
		c[k]=i;
	
		int color=c[k];
		bool check=true;
		for(int i=h[k];i!=-1;i=ne[i])
		{
			int j=e[i];
//			printf("graphcolor:结点%d的颜色为:%d,与其相接的结点%d的颜色为%d\n",k,c[k],j,c[j]);
			if(c[j]==color)
			{	
//				printf("Error!当前结点%d和结点%d颜色相同,为%d\n",k,j,c[k]);
				check=false;
			}
		}
		if(check&&k!=n) 
		{		
//			printf("----当前结点%d的颜色和所邻接的结点不同,当前结点颜色定为%d\n",k,c[k]);
			graphcolor(k+1);
		}
		if(check&&k==n)
		{
			flag=true;
			printf("--------------染色成功!--------------\n");
			for(int i=1;i<=n;i++) printf("%d ",c[i]);
			printf("\n");
			//这里需要注意，不能有return在这里！！！
			//如果有return在这里，就无法“恢复现场”了！！！打印出的结果会变少！！！ 
			//return;
		}
		//"恢复现场"，非常重要！ 
		c[k]=0;
	}
}
//void graphcolor(int k)
//{
//	while(k>=1)
//	{
//		while(c[k]<=2)
//		{	
//			c[k]+=1;
//			bool check=true;
//			for(int i=h[k];i!=-1;i=ne[i])
//			{
//				int j=e[i];
//				if(c[j]==c[k])
//					check=false;
//			}
//			if(k==n&&check)
//			{
//				printf("--------------染色成功!--------------\n");
//				for(int i=1;i<=n;i++)
//					printf("%d ",c[i]);
//				printf("\n");
//			}
//			else if(k<n&&check) k=k+1;
//		}
//		c[k]=0;
//		k-=1;
//	}
//}
int main()
{	
	memset(h,-1,sizeof h);
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
//	for(int k=1;k<=n;k++)
//	{
//		for(int i=h[k];i!=-1;i=ne[i])
//		{	
//			int j=e[i];
//			printf("与结点%d相接的结点有:%d\n",k,j);
//		}
//	}
	for(int i=1;i<=n;i++) c[i]=0;
	graphcolor(1);
	return 0;
}