BZOJ 1006 【HNOI2008】 神奇的国度

题目链接：神奇的国度

　　一篇论文题……神奇的弦图，神奇的MCS……

　　感觉我没有什么需要多说的，这里简单介绍一下MCS：

　　我们给每个点记录一个权值，从后往前依次确定完美消除序列中的点，每次选择权值最大的一个点(相同的话随意选一个)放到当前完美消除序列中的位置，然后把相邻的所有点权值加\(1\)。一路到底即可得到一种完美消除序列。使用链表可以将复杂度优化到\(O(n+m)\)。在弦图中有 最小染色=团数，求完美消除序列的时候顺便统计即可。

　　好吧，上面实在扯淡。其实还是要看\(CDQ\)当年的\(ppt\)才好懂……给个链接：弦图与区间图

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 10010

#define maxm 1000010

using namespace std;

typedef long long llg;

int n,nn,m,a[maxn],best,b[maxn],ans;

int head[maxn],next[maxm<<1],to[maxm<<1],tt;//原图邻接表

int he[maxn],ne[maxm],zh[maxm];//挂链存储

bool vis[maxn];

int getint(){

    int w=0;bool q=0;

    char c=getchar();

    while((c>'9'||c<'0')&&c!='-') c=getchar();

    if(c=='-') c=getchar(),q=1;

    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

    return q?-w:w;

}

void link(int x,int y){

    to[++tt]=y;next[tt]=head[x];head[x]=tt;

    to[++tt]=x;next[tt]=head[y];head[y]=tt;

}

int main(){

    File("a");

    n=nn=getint(); m=getint();

    while(m--) link(getint(),getint()); tt=0;

    for(int i=1;i<=n;i++) zh[++tt]=i,ne[tt]=he[0],he[0]=tt;

    while(best>=0){

        ans=max(ans,best);//统计最大团数

        while(he[best]){

            int u=zh[he[best]],be=0; he[best]=ne[he[best]];

            if(!vis[u]) a[nn--]=u,vis[u]=1;

            else continue;

            for(int i=head[u],v;v=to[i],i;i=next[i])

                if(!vis[v]){

                    b[v]++; zh[++tt]=v;//相邻点权值加1并新建一个节点

                    ne[tt]=he[b[v]]; he[b[v]]=tt;

                    if(b[v]>best) best=b[v],be=1;

                }

            if(be){best++; break;}

        }

        best--;

    }

    printf("%d",ans+1);

    return 0;

}