习题 8-9 K度图的着色（K-Graph Oddity, ACM/ICPC NEERC 2010, UVa1613）

本文主要是介绍习题 8-9 K度图的着色（K-Graph Oddity, ACM/ICPC NEERC 2010, UVa1613），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1613
分类：贪心法
备注：简单思维题

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
vector<int>e[maxn];
int n,m,k,color[maxn];
bool check(int x,int c){for(int i=0;i<e[x].size();i++)if(color[e[x][i]]==c)return false;return true;
}
void dfs(int u){for(int i=0;i<e[u].size();i++){if(color[e[u][i]]==0){for(int j=1;j<=k;j++){if(check(e[u][i],j)){color[e[u][i]]=j;break;}}dfs(e[u][i]);}}
}
int main(void){//freopen("in.txt","r",stdin);while(~scanf("%d %d",&n,&m)){if(e[1].size())printf("\n");memset(color,0,sizeof(color));for(int i=1;i<=n;i++)e[i].clear();for(int i=0;i<m;i++){int a,b; scanf("%d %d",&a,&b);e[a].push_back(b);e[b].push_back(a);}k=0;for(int i=1;i<=n;i++)k=max(k,(int)e[i].size());if(k%2==0)k++;color[1]=1;dfs(1);printf("%d\n",k);for(int i=1;i<=n;i++)printf("%d\n",color[i]);}return 0;
}

这篇关于习题 8-9 K度图的着色（K-Graph Oddity, ACM/ICPC NEERC 2010, UVa1613）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---