[BZOJ1006]神奇的国度

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 10005
 4 #define maxm 1000005
 5 int cnt,v[maxm<<1],next[maxm<<1],first[maxn];
 6 int lab[maxn],vis[maxn],se[maxn],used[maxn],col[maxn];
 7 void add(int st,int end){
 8     v[++cnt]=end;
 9     next[cnt]=first[st];
10     first[st]=cnt;
11 }
12 int main(){
13     int n,m,a,b;
14     scanf("%d%d",&n,&m);
15     for(int i=1;i<=m;i++){
16         scanf("%d%d",&a,&b);
17         add(a,b),add(b,a);
18     }
19     for(int i=n;i;i--){
20         int pos=0;
21         for(int j=1;j<=n;j++)
22             if(!vis[j]&&lab[j]>=lab[pos])pos=j;
23         vis[pos]=1;
24         se[i]=pos;
25         for(int e=first[pos];e;e=next[e])
26             lab[v[e]]++;
27     }
28     int ans=0;
29     for(int i=n;i;i--){
30         for(int e=first[se[i]];e;e=next[e])
31             used[col[v[e]]]=se[i];
32         int j=1;
33         while(used[j]==se[i])j++;
34         col[se[i]]=j;
35         if(j>ans)ans=j;
36     }
37     printf("%d\n",ans);
38     return 0;
39 }