Description
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA
相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2
...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C
D,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，
最少可以分多少支队。
Solution
依旧要放CDQ的论文链接《弦图与区间图》CDQ
嗯这题是弦图的染色问题·裸
弦图的染色 （用最少的颜色给所有点染色使得相邻点颜色不同）
完美消除序列从后往前给每个点染上能染的最小颜色
最大独立集（最大的点的子集使得任意两个点不相邻）
完美消除序列从前往后能选则选
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> 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<t)ans=t; } } int main() { memset(head,-1,sizeof(head)); n=read(),m=read(); for(int i=1;i<=m;i++) { int u,v; u=read(),v=read(); addedge(u,v); addedge(v,u); } work(); printf("%d ",ans); return 0; }