uva1613 K-Graph Oddity

题目要求k>=最大度数；
观察，颜色数量和度数的关系，得颜色数=最大度数+1（偶数）//最大度数（奇数）可以满足染色关系
一个点和周围的点的颜色数加起来最大为它的度数+1；
　k=所有点中最大的度。如果最大入度是偶数，则k+1。
证明：当最大度数为奇数n，设点u所连n个点，点u为1，n-1个点不一样，1个点和某个点相同（2-n），那么其他n-1个点可以相连，度数n-2+1=n-1，如果再连这个相同点，度数为n；然而此时一共有n+1个点，为偶数，所以要再加一个点
如果加到这个点（新的n），最大度数改变，不可以；加到其他点，也不能超过n，所以一定有两个点没有直接相连，交换没有直接相连的点和（新的n那个点），就满足了条件
策略：dfs

k = (max(deg+1,deg+1+n))|1;

#include <iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = ;

const int maxm = ;  //为啥开这么大....用100005re

int head[maxn],to[maxm],nxt[maxm],col[maxn],ecnt,deg[maxn];

int vis[maxn];

int k;

void addEdge(int u,int v)

{

    deg[u]++;

    k=max(k,deg[u]);

    to[ecnt] = v;

    nxt[ecnt] = head[u];

    head[u] = ecnt++;

}

void dfs(int u)

{

    for(int i = head[u]; i!=-; i= nxt[i])

        vis[col[to[i]]] = u;  //u的连接点的颜色都标记为u，不能用

    for(int i = ; 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()

{

    int n,m;

    while(scanf("%d",&n)==){

            k=;

        scanf("%d",&m);

        memset(head,-,sizeof(head));

        memset(deg,,sizeof(deg));

        memset(col,,sizeof(col));

        ecnt = ;

        while(m--){

            int u,v;

            scanf("%d %d",&u,&v);

            addEdge(u,v); addEdge(v,u);

        }

        k = k|;

        memset(vis,,sizeof(vis));

        dfs();

        printf("%d\n",k);

        for(int i = ; i <= n; i++)

            printf("%d\n",col[i]);

        cout<<endl;

    }

    return ;

}

巴特西

uva1613 K-Graph Oddity

最新文章

热门文章