题目描述
K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.
所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。
输入输出格式
输入格式：
第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友
输出格式：
输出一个整数，最少可以分多少队
输入输出样例
输入样例#1：
4 51 21 42 42 33 4
输出样例#1：
3 题目中说只存在“三角关系”，也就是说，原图必是一个弦图 弦图为完美图，必定满足最小色数=最大团点数 求出最大团用MCS(最大势)算法，du[i]为i的势 看不懂？把基础知识补上，这就是模板题 这里MCS用动态数组可以线性O(n+m) 最大团点数=max(du[i]+1)
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 struct Node 9 {10 int next,to;11 }edge[2000001];12 int ans,head[10001],n,m,num,best,flag,r,du[10001];13 bool pd[10001];14 vector G[10001];15 void add(int u,int v)16 {17 num++;18 edge[num].next=head[u];19 head[u]=num;20 edge[num].to=v;21 }22 int main()23 { int i,j,u,v;24 cin>>n>>m;25 for (i=1;i<=m;i++)26 {27 scanf("%d%d",&u,&v);28 add(u,v);add(v,u);29 }30 for (i=1;i<=n;i++)31 G[0].push_back(i);32 best=0;33 for (i=1;i<=n;i++)34 {35 flag=1;36 while (flag)37 {38 for (j=G[best].size()-1;j>=0;j--)39 if (pd[G[best][j]]) G[best].pop_back();40 else41 {r=G[best][j];flag=0;break;}42 if (flag) best--;43 }44 pd[r]=1;45 for (j=head[r];j;j=edge[j].next)46 {47 int v=edge[j].to;48 if (pd[v]) continue;49 G[++du[v]].push_back(v);50 best=max(best,du[v]);51 }52 }53 for (i=1;i<=n;i++)54 ans=max(ans,du[i]+1);55 cout<