Description 给出一张无向图，用至多k种颜色染色，要求相邻两点颜色不同，给出一种合法方案 Input 第一行三整数n,m,k分别表示点数，边数和颜色数，之后m行每行两个整数u和v表示u和v之间有边(1<=n<=1000,0<=m<=n*(n-1)/2,1<=k<=n) Output 如果存在一种合法的染色方案则输出每个点的颜色，否则输出-1 Sample Input 3 2 2 1 2 2 3 Sample Output 1 2 1 Solution 简单题，暴力染色然后判合法即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 1111 int n,m,k,g[maxn][maxn],flag[maxn],c[maxn]; int main() { while(~scanf("%d%d%d",&n,&m,&k)) { memset(g,0,sizeof(g)); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); g[u][v]=g[v][u]=1; } memset(c,0,sizeof(c)); for(int u=1;u<=n;u++) if(!c[u]) { memset(flag,0,sizeof(flag)); for(int v=1;v<=n;v++) if(v!=u&&g[v][u]&&c[v])flag[c[v]]=1; int temp=1; while(flag[temp])temp++; c[u]=temp; } int gg=0; for(int i=1;i<=n&&!gg;i++) { if(c[i]>k)gg=1; for(int j=i+1;j<=n&&!gg;j++) { if(g[i][j]&&c[i]==c[j])gg=1; if(!g[i][j]&&c[i]!=c[j])gg=1; } } if(gg)printf("-1\n"); else { for(int i=1;i<=n;i++) printf("%d%c",c[i],i==n?'\n':' '); } } return 0; }