題意：輸入n個點m條邊的聯(lián)通圖，n為奇數(shù)，設(shè)k為最小的奇數(shù)，使得每個點的度數(shù)不超過k，要求把節(jié)點都涂上顏色，使得相鄰節(jié)點顏色不一樣。

思路：dfs。k的值為奇數(shù)，所以k為節(jié)點最大度數(shù)（+1）。從當(dāng)前節(jié)點往下找，如果下邊的節(jié)點沒有染色，就把當(dāng)前節(jié)點染色繼續(xù)下找。

code：

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <sstream> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <bitset>using namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;const int INF=0x3fffffff; const int inf=-INF; const int N=10005; const int M=2005; const int mod=1000000007; const double pi=acos(-1.0);#define cls(x,c) memset(x,c,sizeof(x)) #define cpy(x,a) memcpy(x,a,sizeof(a)) #define fr(i,s,n) for (int i=s;i<=n;i++) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define lowbit(x) (x&-x) #define pii pair<int,int> #define mk make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout);int s[N],vis[N]; vector<int>g[N]; int k,n,m;void dfs(int u) {cls(vis,0);vector<int>ne;for (int i=0;i<g[u].size();++i){int v=g[u][i];if (s[v]) vis[s[v]]=1;else ne.push_back(v);}for (int i=1;i<=k;i++){if (!vis[i]) {s[u]=i;break;}}for (int i=0;i<ne.size();i++){if (!s[ne[i]]) dfs(ne[i]);} } int main() {int a,b,ca=0;while (~scanf("%d %d",&n,&m)){if (ca++) puts("");for (int i=0;i<n;i++) g[i].clear();for (int i=0;i<m;i++){scanf("%d %d",&a,&b);g[a-1].push_back(b-1);g[b-1].push_back(a-1);}cls(s,0);k=-1;for (int i=0;i<n;i++) k=max(k,(int)g[i].size());if (k%2==0) k++;printf("%d\n",k);dfs(0);for (int i=0;i<n;i++) printf("%d\n",s[i]);} }

總結(jié)

以上是生活随笔為你收集整理的uva 1613——K-Graph Oddity的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。