bzoj1006--神奇的国度

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

#define max(a,b) a>b?a:b
const int maxn=10000+10000;

vector<int>G[maxn];
vector<int>du[maxn];
bool vis[maxn];
int d[maxn];
int q[maxn];
int check[maxn];
int col[maxn];
int Maxdu;

int main(){
  
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i++){
    
    int u,v;
    scanf("%d%d",&u,&v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  Maxdu=0;
  for(int i=1;i<=n;i++) du[Maxdu].push_back(i),vis[i]=false,d[i]=0;
  for(int i=1;i<=n;i++){
  
    while(du[Maxdu].empty()){
      
      Maxdu--;
      if(du[Maxdu].empty()) continue;
      while(!du[Maxdu].empty()&&vis[*(du[Maxdu].begin())]) du[Maxdu].erase(du[Maxdu].begin()); 
    }
    int node=du[Maxdu][0];
    du[Maxdu].erase(du[Maxdu].begin());
    vis[node]=true;
    q[i]=node;
    int len=G[node].size();
    for(int j=0;j<len;j++){
      
      int v=G[node][j];
      if(!vis[v]){
        
        d[v]++;
        du[d[v]].push_back(v);
        Maxdu=max(Maxdu,d[v]);
      }
    } 
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    
    int node=q[i];
    int len=G[node].size();
    for(int j=0;j<len;j++){
      
      int v=G[node][j];
      check[col[v]]=i;
    }
    int j;
    for(j=1;;j++) if(check[j]!=i) break;
    col[node]=j;
    if(j>ans) ans=j;
  }
  printf("%d\n",ans);
}