1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,ll> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn=10000+5;17 18 int n, m;19 int head[maxn];20 int tot;21 int ans;22 int label[maxn]; //label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号23 int vis[maxn];24 int q[maxn];25 int check[maxn];26 int col[maxn];27 28 struct node29 {30     int v;31     int next;32 }e[2*1000000+1000];33 34 void addEdge(int u, int v)35 {36     e[tot].v=v;37     e[tot].next=head[u];38     head[u]=tot++;39 }40 41 void MCS()  //最大势算法求完美消除序列42 {43     memset(vis,0,sizeof(vis));44     for(int i=n;i;i--)45     {46         int pos=0;47         for(int j=1;j<=n;j++)   //选择当前未访问且label值最大的48             if(!vis[j] && label[j]>=label[pos])   pos=j;49         vis[pos]=1;50         q[i]=pos;51         for(int j=head[pos];j!=-1;j=e[j].next)  //与pos结点相邻的结点label值+152             label[e[j].v]++;53     }54 }55 56 void color()//染色57 {58     memset(check,0,sizeof(check));59     memset(col,0,sizeof(col));60     for(int i=n;i;i--)61     {62         int pos=q[i],j;63         for(int j=head[pos];j!=-1;j=e[j].next)  check[col[e[j].v]]=i;64         for(j=1;;j++)  if(check[j]!=i)  break;65         col[pos]=j;66         if(j>ans)  ans=j;67     }68 }69 70 int main()71 {72     //freopen("in.txt","r",stdin);73     while(~scanf("%d%d",&n,&m))74     {75         tot=0;76         memset(head,-1,sizeof(head));77         while(m--)78         {79             int u,v;80             scanf("%d%d",&u,&v);81             addEdge(u,v);82             addEdge(v,u);83         }84         ans=0;85         MCS();86         color();87         printf("%d\n",ans);88     }89     return 0;90 }