Luogu

BZOJ

分析

转换一下题目模型,变成了一个「弦图最小染色问题」。

CDQ的课件(点击下载)告诉我们,可以用「最大势算法」来做这个题。

具体是求出完美消除序列,然后从后往前依次给每个点染上可以染的最小的颜色。

然而本题只要求出颜色个数,可以证明答案为$\max\limits_{i=1}^nlabel[i]+1$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=10000+10;
const int MAXM=1000000+10;

struct Edge { int v,nxt; };
Edge e[MAXM<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int label[MAXN],vis[MAXN];
int Q[MAXN],tot=0;
vector<int> V[MAXN];

int main() {
    int n=read(),m=read();
    for (re int i=1,u,v;i<=m;++i) {
        u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) V[0].push_back(i);
    int best=0;
    for (re int i=1,now=0;i<=n;++i) {
        int flag=0;
        while (!flag) {
            for (re int j=V[best].size()-1;j>=0;--j) {
                if (vis[V[best][j]]) V[best].pop_back();
                else { flag=1; now=V[best][j]; break; }
            }
            if (!flag) --best;    
        }
        Q[++tot]=now,vis[now]=1;
        for (re int j=head[now];j;j=e[j].nxt) {
            int v=e[j].v;
            if (!vis[v])
                V[++label[v]].push_back(v),best=max(best,label[v]);
        }
    }
    int ans=0;
    for (re int i=1;i<=n;++i) ans=max(ans,label[i]+1);
    printf("%d\n",ans);
    return 0;
}

版权属于:M_sea

本文链接:https://m-sea-blog.com/archives/1664/

转载时须注明出处及本声明

最后修改:2020 年 02 月 18 日 09 : 47 AM