【BZOJ1006】神奇的国度

    参考cdq《弦图与区间图》，MCS最大势算法。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=10010,maxm=1000010;
 
struct List
{
    struct Node
    {
        Node *prev,*next;
        int w,id;
    }*H[maxn],*ID[maxn],*Null,*High;
     
    void Delete(Node *x)
    {
        x->prev->next=x->next;
        x->next->prev=x->prev;
        x->prev=x->next=Null;
        while (High!=H[0] && High->next==Null) High=H[High->w-1];
    }
 
    void Add_List(Node *x,int w)
    {
        Delete(x);
        x->w=w;
        x->prev=H[w];
        x->next=H[w]->next;
        H[w]->next->prev=x;
        H[w]->next=x;
    }
 
    void Init(int n)
    {
        for (int i=0;i<=n;i++) ID[i]=new Node,H[i]=new Node;
        Null=new Node;
        Null->prev=Null->next=Null;
        Null->w=0;
        High=H[0];
        for (int i=0;i<=n;i++) H[i]->prev=H[i]->next=ID[i]->prev=ID[i]->next=Null,H[i]->w=i,ID[i]->w=0,ID[i]->id=i;
        for (int i=1;i<=n;i++) Add_List(ID[i],0);
    }
 
    void Up(int x) {Add_List(ID[x],ID[x]->w+1);if (High->w<ID[x]->w) High=H[ID[x]->w];}
    void Delete(int x) {Delete(ID[x]);}
    int MaxD() {return High->next->id;}
}L;
 
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
 
int used[maxn];
int In[maxn];
int Color[maxn];
int head[maxn],next[maxm<<1],E[maxm<<1],Ecnt;
int n,m,maxc;
 
void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}
 
int main()
{
    read(n),read(m);
    L.Init(n);
    for (int i=1,x,y;i<=m;i++) read(x),read(y),Add_Edge(x,y);
    for (int i=1;i<=n;i++)
    {
        int x=L.MaxD();
        L.Delete(x);
        In[x]=1;
        for (int j=head[x];j;j=next[j]) if (!In[E[j]]) L.Up(E[j]);
            else used[Color[E[j]]]=i;
        Color[x]=1;
        while (used[Color[x]]==i) Color[x]++;
        if (Color[x]>maxc) maxc=Color[x];
    }
    printf("%d\n",maxc);
    return 0;
}