UVA-1613 K-Graph Oddity (着色问题)

时间:2022-02-02 18:43:44

题目大意:一张n个顶点、m条边的无向连通图,用k种颜色着色(相邻顶点颜色不能相同),其中k为不小于点的最大度数的最小奇数。

题目分析:水题一道。建张图深搜一下就行了。

# include<iostream>
# include<cstdio>
# include<set>
# include<cstring>
# include<algorithm>
using namespace std; struct Edge
{
int to,nxt;
};
Edge e[200005];
int n,m,k,du[10000],head[10000],color[10000],cnt;
set<int>s[10000]; void add(int u,int v)
{
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt++;
} void dfs(int u)
{
for(set<int>::iterator it=s[u].begin();it!=s[u].end();++it){
color[u]=*it;
for(int i=head[u];i!=-1;i=e[i].nxt)
if(!color[e[i].to])
s[e[i].to].erase(*it);
for(int i=head[u];i!=-1;i=e[i].nxt)
if(!color[e[i].to])
dfs(e[i].to);
break;
}
} int main()
{
int a,b,flag=0;
while(scanf("%d%d",&n,&m)==2)
{
if(flag)
printf("\n");
flag=1;
cnt=0;
memset(du,0,sizeof(du));
memset(color,0,sizeof(color));
memset(head,-1,sizeof(head));
while(m--)
{
scanf("%d%d",&a,&b);
++du[a],++du[b];
add(a,b);
add(b,a);
}
k=0;
for(int i=1;i<=n;++i)
k=max(k,du[i]);
if(k%2==0)
++k;
printf("%d\n",k);
for(int i=1;i<=n;++i){
s[i].clear();
for(int j=1;j<=k;++j)
s[i].insert(j);
}
dfs(1);
for(int i=1;i<=n;++i)
printf("%d\n",color[i]);
}
return 0;
}