UVA-1613 K-Graph Oddity （着色问题）

题目大意：一张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("
");
        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
",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
",color[i]);
    }
    return 0;
}