题解:

　　MCS算法.详细说明请见cdq的论文--弦图和区间图.

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #define MAXN 100001011 #define RG register12 #define LL long long int13 using namespace std;14 const int INF=1e9;15 const int mod=31011;16 struct node{17 int next;18 int to;19 }t[MAXN*2];20 int head[MAXN*2],num;21 int n,m;22 int ans;23 int du[MAXN],vis[MAXN],q[MAXN];24 int col[MAXN],used[MAXN];25 void add(int from,int to)26 {27 t[++num].next=head[from];28 t[num].to=to;29 head[from]=num;30 }31 int main()32 {33 freopen("1.in","r",stdin);34 scanf("%d%d",&n,&m);int x,y;35 for(int i=1;i<=m;i++){36 scanf("%d%d",&x,&y);add(x,y);add(y,x);37 }38 for(int i=n;i>=1;i--){39 int p=0;40 for(int j=1;j<=n;j++) if(!vis[j] && du[j]>=du[p]) p=j;41 q[i]=p;vis[p]=1;42 for(int j=head[p];j;j=t[j].next) du[t[j].to]++;43 }44 for(int i=n;i>=1;i--){45 int p=q[i];46 for(int j=head[p];j;j=t[j].next) used[col[t[j].to]]=p;47 int j;48 for(j=1;;j++) if(used[j]!=p) break;49 col[p]=j;if(j>ans) ans=j;50 }51 printf("%d\n",ans);52 return 0;53 }