[UVa 1613][POJ 3969]K-Graph Oddity

假設某個點的度數$<K$，那麼我們就乾脆先把其他點著色，再來決定這點要著甚麼顏色就好啦

可以發現，本題條件限制$K$和$N$都要是奇數，因此一定有一點的度數$<K$ (想一想，為甚麼XD)
找到這點後，把它從圖上移除，為剩餘的圖著色，這時相鄰的點的度數一定都$<K$，再把它移除，為剩餘的圖著色，......

這樣下去，會剩下一個點，把它塗成顏色1，然後慢慢把刪除的點加回去並著色，這樣整張圖就著色完成了！

把點移除真麻煩？
其實不用真的移除啦

我們只需要從某個度數$<K$的點開始dfs，當走到$u$時，先把$u$的子節點著色 (往$u$的子節點dfs)，再把$u$著色

時間複雜度：$O(N+M)$

p.s.重度優化後在POJ上還是TLE，但是在UVa上獲得第一名惹Orz
p.s.後來在網路上發現網友的解法，還真的可以在POJ上AC，他是用bfs的逆順序著色 (吧?)，是說......POJ有這麼恨遞迴嗎!@#%^&*......

code:

#include<cstdio>
#include<vector>
using namespace std;
const int INF=2147483647;
int N,M,K,ANS[9999],CNT[10000];
vector<int>ET[9999];
bool VIS[9999];
void Dfs(const int u)
{
    VIS[u]=true;
    for(int i=0;i<(int)ET[u].size();i++)if(!VIS[ET[u][i]])Dfs(ET[u][i]);//先把子節點著色 
    int sum=0;
    for(int i=0;i<(int)ET[u].size();i++)if(ANS[ET[u][i]]!=-1)CNT[ANS[ET[u][i]]]++,sum++;
    int &ans=ANS[u]=0;
    while(CNT[ans]>0&&sum-->0)ans++;//決定u著甚麼顏色，那個sum是沒用的，只是讓你知道迴圈最多執行這麼多回
    for(int i=0;i<(int)ET[u].size();i++)if(ANS[ET[u][i]]!=-1)CNT[ANS[ET[u][i]]]--;//把CNT還原
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0,a,b;i<M;i++)scanf("%d%d",&a,&b),a--,b--,ET[a].push_back(b),ET[b].push_back(a);//這邊只有建圖，容我縮成一行吧XD 
        K=0;
        for(int i=0;i<N;i++)if((int)ET[i].size()>K)K=(int)ET[i].size();
        if(K%2==0)K++;//算出K 
        for(int i=0;i<=K;i++)CNT[i]=0;
        int mn=INF,source=-1;
        for(int i=0;i<N;i++)if((int)ET[i].size()<mn)mn=(int)ET[i].size(),source=i;//找出度數最少的點，保證度數<K 
        for(int i=0;i<N;i++)VIS[i]=false,ANS[i]=-1;
        Dfs(source);
        static int kase=0;
        if(kase++)puts("");
        printf("%d\n",K);
        for(int i=0;i<N;i++)printf("%d\n",ANS[i]+1);
    }
    return 0;
}