发布时间: 2017年4月4日 20:22 最后更新: 2017年4月4日 20:23 时间限制: 1000ms 内存限制: 128M
描述喵哈哈村最近生活的很平静，于是月亮同学就决定出一道题给星星同学玩：
上周月亮同学偷偷的去看了《嫌疑人X的献身》这部电影，其中的男主角就整天抱着四色问题这本书，现在月亮同学就准备考考很蠢的星星同学。
给出一个平面图，这个图由n个点，m条无向边组成。
现在你需要对每个点染色，使得每一个边相连的点的颜色都不一样。
请问最少使用多少个颜色。
输入本题包含若干组测试数据。 第一行两个整数n，m，表示点数和边数。保证无重边，无自环。 满足 1<=n<=10,0<=m<=n*(n-1)/2
输出输出最少颜色数量
样例输入1 复制 3 3 1 2 2 3 1 3 样例输出1 3 查看隐藏信息 选择语言C (GCC 4.8) C++ (G++ 4.3) Java (Oracle JDK 1.7)
典型搜索，n=10，所以直接枚举每一点所染的颜色即可
#include <stdio.h> #include <string.h> #include <stdlib.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; #define maxn 15 int a[maxn][maxn],b[maxn];//b数组存放点i所染的颜色 int n,m,flag; void dfs(int x,int y) { if(flag) return; if(x==n+1) { flag=1; return; } for(int i=1;i<=min(x,y);i++) { b[x]=i; int mark=0; for(int j=1;j<x;j++) if(a[j][x] && b[x]==b[j]) { mark=1; break; } if(mark==0) dfs(x+1,y); } } int main(void) { int i,x,y; while(scanf("%d%d",&n,&m)!=EOF) { memset(a,0,sizeof(a)); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); a[x][y]=1; a[y][x]=1; } for(i=1;i<=n;i++) { flag=0; dfs(1,i); if(flag) { printf("%d\n",i); break; } } } return 0; }
