听LLJ大佬说要学奇怪的算法来增长姿势。
原题可以翻译为给一个无向图染色，保证有连边的两点颜色不同，问最少的颜色数。
用最大势算法。有n+m的写法，但是在下不会，就用个堆。
把每个点势初始为0，扔进去，每次取出最大的，和他相连的没被删掉的点势++，删掉他。
代码很好写啊，在下觉得十分有道理。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
typedef long long LL;
using namespace std;
const int maxn=10000+299;
const int maxm=1000000*2+299;
int n,m,x,y,fir[maxn],nxt[maxm],to[maxm],ecnt,ok[maxn],du[maxn],ans;
struct node {
int x,d;
friend bool operator <(const node&a,const node&b) {
return a.d<b.d;
}
node(int x,int d):x(x),d(d){}
};
void add(int x,int y) {
nxt[++ecnt]=fir[x]; fir[x]=ecnt; to[ecnt]=y;
nxt[++ecnt]=fir[y]; fir[y]=ecnt; to[ecnt]=x;
}
priority_queue<node>que;
void init() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
add(x,y);
}
}
void work() {
for(int i=1;i<=n;i++) que.push(node(i,0));
while(!que.empty()) {
node now=que.top();
que.pop();
int x=now.x,d=now.d;
if(!ok[x]) {
for(int i=fir[x];i;i=nxt[i]) if(!ok[to[i]]){
ans=max(ans,++du[to[i]]);
que.push(node(to[i],du[to[i]]));
}
ok[x]=1;
}
}
printf("%d
",ans+1);
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
init();
work();
return 0;
}