记录编号	141285	评测结果	AAAAAAAAAA
题目名称	1830.[HNOI 2008]神奇的国度	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.864 s
提交时间	2014-11-30 16:03:42	内存使用	0.51 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
const int maxn = 10002;
vector<int> adj[maxn];
int N, color[maxn] = {0}, ans = 0, adjcnt[maxn] = {0};
inline void init(){
	int a, b, M;
	getd(N), getd(M);
	while(M--){
		getd(a), getd(b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
}
inline void work(){
	int i, j, lim, tmp = 1, Max = 0;
	bool ok_col[maxn];
	lim = (int)adj[1].size();
	color[1] = 1;
	for(i = 0;i < lim;++i)
		if(!color[adj[1][i]]) ++adjcnt[adj[1][i]];
	for(i = 1;i < N;++i){
		Max = 0;
		for(j = 1;j <= N;++j){
			ok_col[j] = 1;
			if(!color[j] && adjcnt[j] > Max)tmp = j, Max = adjcnt[j];
		}
		lim = (int)adj[tmp].size();
		for(j = 0;j < lim;++j)
			ok_col[color[adj[tmp][j]]] = 0;
		for(j = 1;j <= N;++j) if(ok_col[j])break;
		color[tmp] = j;
		if(j > ans)ans = j;
		lim = (int)adj[tmp].size();
		for(j = 0;j < lim;++j)
			if(!color[adj[tmp][j]]) ++adjcnt[adj[tmp][j]];
	}
	printf("%d\n", ans);
}
int main(){
	freopen("bzoj_1006.in", "r", stdin);
	freopen("bzoj_1006.out", "w", stdout);
	init();
	work();
	return 0;
}