uva 1613——K-Graph Oddity

雨点打透心脏的1/2处 2022-08-10 00:58 18阅读 0赞

题意：输入n个点m条边的联通图，n为奇数，设k为最小的奇数，使得每个点的度数不超过k，要求把节点都涂上颜色，使得相邻节点颜色不一样。

思路：dfs。k的值为奇数，所以k为节点最大度数（+1）。从当前节点往下找，如果下边的节点没有染色，就把当前节点染色继续下找。

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]);
        }
    }