弦图染色

对于一般图，有性质最小染色数>=最大团

我们先用最大势求出完美消除序列，再逆序贪心涂色

正确性：

容易发现这样的涂色数=最大团数

而当前涂色数>=最小染色数

所以弦图最小染色数=最大团数

顺便放个：弦图还有一个这样的性质，最大独立集=最小团覆盖数，而在普通的图中是前者<=后者的

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;struct node{ int x,y,next;}a[2100000],e[2100000];int len,last[11000],elen,elast[11000];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}void eins(int x,int y){ elen++; e[elen].x=x;e[elen].y=y; e[elen].next=elast[x];elast[x]=elen;}int n,lab[11000],vq[11000];bool b[11000];void relab(){ int p=0,x; for(int i=1;i<=n;i++)eins(0,i); for(int i=n;i>=1;i--) { x=-1; while(x==-1) { int pre; for(int k=elast[p];k;pre=k,k=e[k].next) { int y=e[k].y; if(b[y]==false)x=y; else { if(k==elast[p])elast[p]=e[k].next; else e[pre].next=e[k].next; } } p--; } p++; vq[i]=x;b[x]=true; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(b[y]==false) { lab[y]++; eins(lab[y],y); p=max(p,lab[y]); } } }}int co,c[11000];int ti,tim[11000];void paint(){ co=ti=0; for(int i=n;i>=1;i--) { int x=vq[i]; ti++; for(int k=last[x];k;k=a[k].next)tim[c[a[k].y]]=ti; for(int j=1;;j++) if(tim[j]!=ti){c[x]=j;break;} co=max(co,c[x]); }}int main(){ int m,x,y; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(x,y),ins(y,x); } relab(); paint(); printf("%d\n",co); return 0;}