題意：在一個(gè)n個(gè)點(diǎn)的無(wú)向連通圖中，n是奇數(shù)，k是使得所有點(diǎn)的度數(shù)不超過(guò)k的最小奇數(shù)，詢問(wèn)一種染色方案，使得相鄰點(diǎn)的顏色不同。

題解：一個(gè)點(diǎn)和周圍的點(diǎn)的顏色數(shù)加起來(lái)最大為它的度數(shù)+1；如果最大度數(shù)是偶數(shù)，那么k種顏色一定夠了。如果最大度數(shù)是奇數(shù)，而且n是奇數(shù)，那么k種顏色也一定是足夠的。 可以反證，最大度數(shù)的點(diǎn)是u，deg[u]是奇數(shù)，而且和u相鄰的點(diǎn)顏色各不相同，那么與u的一個(gè)相鄰點(diǎn)v，至少和deg[u]個(gè)顏色不同的點(diǎn)相鄰，這樣構(gòu)造出來(lái)連通圖點(diǎn)數(shù)一定是偶數(shù)，和n是奇數(shù)是矛盾的，所以不會(huì)出現(xiàn)顏色數(shù)為deg[u]+1的情況。

所以只要染色就好了。

#include<bits/stdc++.h> using namespace std; const int maxn = 1e4; const int maxm = 2e5+5;int head[maxn],to[maxm],nxt[maxm],col[maxn],ecnt,deg[maxn]; int vis[maxn];void addEdge(int u,int v) {deg[u]++;to[ecnt] = v;nxt[ecnt] = head[u];head[u] = ecnt++; } int k;void dfs(int u) {for(int i = head[u]; ~i; i= nxt[i]){vis[col[to[i]]] = u;}for(int i = 1; i <= k; i++) if(vis[i] != u) { col[u] = i; break; }for(int i = head[u]; ~i; i= nxt[i]){if(col[to[i]]) continue;dfs(to[i]);} }int main() {//freopen("in.txt","r",stdin);int n,m;while(~scanf("%d",&n)){scanf("%d",&m);memset(head+1,-1,sizeof(int)*n);memset(deg+1,0,sizeof(int)*n);memset(col+1,0,sizeof(int)*n);ecnt = 0;while(m--){int u,v;scanf("%d %d",&u,&v);addEdge(u,v); addEdge(v,u);}k = (*max_element(deg+1,deg+1+n))|1;memset(vis+1,0,sizeof(int)*k);dfs(1);printf("%d\n",k);for(int i = 1; i <= n; i++) printf("%d\n",col[i]);putchar('\n');}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/jerryRey/p/4702323.html

總結(jié)

以上是生活随笔為你收集整理的UVA 1613 K-Graph Oddity K度图着色 （构造）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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