膜了一上午CDQ的弦图课件

真尼玛一堆性质/定理

不过基本上懂了

这题就是直接用，首先用MCS求完美消除序列。然后有一个性质：最大团=最小染色数。

看网上一堆人写的好长贪心求染色的都是没看到这个性质就弃坑了么= =。

然后就直接求个最大团就可以了。还有个性质就是最大团为每个点跟其完美消除序列位置后面相连的点的导出子图是一个团

所以只要枚举每个点看其连的点里面有多少个在其前面就可以了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 1000050
#define fr first
#define sc second
int c[M*2][2],ss=1,fi[N],n,m,ans,sg[N],s[N];bool b[N];
priority_queue <pair<int,int> > li;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line(int x,int y)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 }
void Solve()
 {
 	for (int i=1;i<=n;i++)
 	  li.push(make_pair(0,i));
 	for (int t=n;t>=1;t--)
 	 {
 	 	do sg[t]=li.top().sc,li.pop(); while (b[sg[t]]);
 	 	b[sg[t]]=1;
 	 	for (int i=fi[sg[t]];i;i=c[i][1])
 	 	 if (!b[c[i][0]])
 	 	   li.push(make_pair(++s[c[i][0]],c[i][0]));
 	 }
 	for (int i=n;i>=1;i--)
 	 {
 	 	int k=0;b[sg[i]]=0;
 	 	for (int j=fi[sg[i]];j;j=c[j][1])
 	 	 if (!b[c[j][0]]) k++;
 	 	ans=max(ans,k+1);
 	 }
 }
int main()
 {
 	n=Read();m=Read();
 	for (int i=1;i<=m;i++)
 	  Line(Read(),Read());
 	Solve();
 	cout <<ans<<endl;
 	return 0;
 }