Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

Input

第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友

Output

输出一个整数，最少可以分多少队

Sample Input

4 5

1 2

1 4

2 4

2 3

3 4

Sample Output

3

HINT

一种方案(1,3)(2)(4)

 

 

 

 

 

这道题，嘿嘿........

CLJ大神说染色问题貌似是NP完全问题，话说NP问题是神马啊？？但此题因为具有一些特别的性质，所以有专门的解法。

百度了一下说要用到一个叫弦图的东西，这里只做简略介绍，弦图具体的讲解可以百度 陈丹琦的《弦图与区间图》。

 

 

 

¨弦(chord)：连接环中不相邻的两个点的边。

¨弦图(chordalgraph)：一个无向图称为弦图当且仅当图中任意长度大于3的环都至少有一个弦。

¨单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v} + N(v)的诱导子图为一个团。

¨完美消除序列(perfect elimination ordering)：这是一个序列{v[i]}，它满足v[i]在{v[i..n]}的诱导子图中为单纯点。

¨弦图的判定：存在完美消除序列的图为弦图。可以用MCS最大势算法求出完美消除序列。

¨最大势算法 Maximum Cardinality Search

·从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。

·设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。

¨判断一个序列是否为完美消除序列

·设{vi+1,…,vn}中所有与vi相邻的点依次为vj1,…, vjk。只需判断vj1是否与vj2,…, vjk相邻即可。

¨本题就是用最少的颜色给每个点染色使得相邻的点染的颜色不同。

¨完美消除序列从后往前依次给每个点染上可以染的最小的颜色。

 

3.扩展

    弦图的方法有着很多经典用途：例如用最少的颜色给每个点染色使得相邻的点染的颜色不同，通过完美消除序列从后往前依次给每个点染色，给每个点染上可以染的最小的颜色；最大独立集问题，选择最多的点使得任意两个点不相邻，通过完美消除序列从前往后能选就选。

    我们再引入区间图的思想，会惊奇地发现它也是弦图。给定一些区间，定义一个相交图为每个顶点表示一个区间，两个点有边当且仅当两个区间的交集非空，如下图所示的区间图：

很显然区间图一定是弦图。这是因为如果存在一个长度大于3的无弦环，刚Ii与Ii+1相交的部分pi一定严格递增或严格递减，以递增为例，即p1 < pn。但由于第一个I1与最后一个In相交刚得出pn < p1产生矛盾。所以区间图一定是弦图。给定n个区间，要求选择最多的区间使得区间不互相重叠，这个问题就是区间图的最大独立集问题。

 

完美消除序列从后往前依次给每个点染上可以染的最小的颜色（为什么？？？？？？）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define Node 10010  6 #define Edg 2000010 7 using namespace std; 8   9 int n,m,ans=0,head[Node],next[Edg],to[Edg],edgs=0;10 int hash[Node],color[Node]={
    0},label[Node]={
    0},v[Node]={
    0},a[Node]={
    0};11  12 void Add(int a,int b){13      edgs++;to[edgs]=b;next[edgs]=head[a];head[a]=edgs;14      }15  16 int main()17 {18     cin>>n>>m;19      20     for(int i=1;i<=n;++i)21     head[i]=-1;22     for(int i=1;i<=m;++i)23     {24       int a,b;cin>>a>>b;25       Add(a,b);Add(b,a);26             }27      28     label[0]=-1;29     for(int i=n;i>=1;--i)30     {31       int k=0;32       for(int j=1;j<=n;++j)33       if(label[j]>label[k]&&!v[j]) k=j;34       a[i]=k;v[k]=1;35        36       for(int j=head[k];j!=-1;j=next[j])37       label[to[j]]++;38             }39      40     for(int i=n;i>=1;--i)41     {42       for(int j=head[a[i]];j!=-1;j=next[j])43       hash[color[to[j]]]=i;44        45       int j=0;46       while(hash[++j]==i); 47       color[a[i]]=j;    48             }49      50     for(int i=1;i<=n;++i)51     if(color[i]>ans) ans=color[i];52      53     cout<
          
           <