题目链接：神奇的国度
一篇论文题……神奇的弦图，神奇的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;
}