Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA

相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2

...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C

D,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，

最少可以分多少支队。

 

Solution

依旧要放CDQ的论文链接

嗯这题是弦图的染色问题·裸

弦图的染色 （用最少的颜色给所有点染色使得相邻点颜色不同）

完美消除序列从后往前给每个点染上能染的最小颜色

最大独立集（最大的点的子集使得任意两个点不相邻）

完美消除序列从前往后能选则选

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,ans=0;int col[10005],check[10005],label[10005],num[10005],head[10005],cnt=0;bool vis[10005];struct Node{    int next,to;}Edges[2000005];void addedge(int u,int v){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;}int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){        if(c=='-')f=-1;c=getchar();    }    while(c>='0'&&c<='9'){        x=x*10+c-'0';c=getchar();    }    return x*f;}void work(){    for(int i=n;i>0;i--)    {        int u=0;        for(int j=1;j<=n;j++)        if(!vis[j]&&(!u||label[j]>label[u]))u=j;        vis[u]=1;num[i]=u;        for(int i=head[u];~i;i=Edges[i].next)        label[Edges[i].to]++;    }    for(int i=n;i>0;i--)    {        for(int j=head[num[i]];~j;j=Edges[j].next)        check[col[Edges[j].to]]=i;        int t=1;        while(check[t]==i)t++;        col[num[i]]=t;        if(ans