题意;

　　在一个n个点的无向连通图中，n是奇数，k是使得所有点的度数不超过k的最小奇数，询问一种染色方案，使得相邻点的颜色不同。

分析：

　　k=所有点中最大的入度。如果最大入度是偶数，则k+1。每个点可选择的颜色是k-他的入度。之后进行染色。先从可选择颜色少的点进行染色，这样最后一个点一定有颜色可以染。

代码：

　　

#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; int n,m; int k; int vis[10010]; int color[10010]; vector
         
          g[10010]; int main() { while(~scanf("%d%d",&n,&m)) { int i,j; for(i=1;i<=n;i++) { g[i].clear(); } memset(vis,0,sizeof(vis)); memset(color,0,sizeof(color)); int maxd=0; for(i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); vis[x]++; vis[y]++; g[x].push_back(y); g[y].push_back(x); maxd=max(max(vis[x],vis[y]),maxd); } if(maxd%2==0) k=maxd+1; else k=maxd; for(i=1;i<=n;i++) { vis[i]=k-vis[i]; } for(i=1;i<=n;i++) { int p; int min_degree=20000; for(j=1;j<=n;j++) { if(color[j]==0&&min_degree>vis[j]) { min_degree=vis[j]; p=j; } } int map[10010]; memset(map,0,sizeof(map)); for(j=0;j