2016年2月9日 星期二

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原