题解 P3196 【[HNOI2008]神奇的国度】

kczno1 · 2017-03-17 22:45:36 · 题解

求弦图点色数。

考虑按完美消除序列从后往前，每个点贪心选择最小可染颜色，

那么他会产生的颜色种类<=所在团大小，

而一个团由于两两连边，每个点颜色都不同，所以产生的颜色种类>=团的大小，

所以弦图点色数就是弦图最大团的大小。

得到完美消除序列用最大势算法，每次选择与最多已选择点相连的点，

由于每次势最多+1,可以对每个值开个双向链表存势为该值的点，可以做到O(1)删除插入，

这样时间就是线性。

之后判断弦图就从后往前扫，检验x与相连的后面的点N(x)是否构成一个团，

就是先找到N(x)里最小的，之后检验他与N(x)其他点是否相连( 用hash表，bitset(压空间)存都是O(1)的 )，

如果不相连显然就不是团，如果相连，由于在他检验的时候已经保证N(x)是个团，那么加入一个和所有点都有连边的点显然还是一个团。

这样每条边只被枚举一次，也是线性的。

(当然这题不需要判断)

#include<cstdio> 

#define N 10010
#define M 1000100
int n,m,i,x,y,k;
int t[N];
struct edge
{
    int to,next;
}l[M<<1];int e;
void add_e(int x,int y)
{
    l[++e]=(edge){y,t[x]};t[x]=e;
}

int next[N<<1],pre[N<<1];
int w[N],q[N],dy[N];

void push(int x)
{
    pre[next[x]=next[N+w[x]]]=x;
    next[pre[x]=N+w[x]]=x;
}
void del(int x)
{
    pre[next[x]]=pre[x];next[pre[x]]=next[x];
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        add_e(x,y);add_e(y,x); 
    }
    for(i=1;i<=n;++i) push(i);
    int now=0,ans=0;
    for(k=n;k;--k,++now)
    {
        while(!next[N+now])--now;
        x=next[N+now];
        del(x);
        q[k]=x;dy[x]=k;
        int sum=1;
        for(i=t[x];y=l[i].to;i=l[i].next)
        if(!dy[y]) 
        {
            del(y);
            ++w[y];
            push(y);
        }
        else ++sum;
        if(sum>ans)ans=sum;
    }
    printf("%d\n",ans);
}