减舟's Blog

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector <int> g[10001];
int n, m, ans = 0, sum[10001], list[10001], color[10001], hash[10001];
bool mark[10001];
void init() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int i = 1, x, y; i <= m; i++) {
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
}
int main() {
	init();
	for (int i = n; i; i--) {
		int t = 0;
		for (int j = 1; j <= n; j++)
			if (!mark[j] && sum[j] >= sum[t]) t = j;
		mark[t] = true; list[i] = t;
		for (int j = 0; j < g[t].size(); j++)
			sum[g[t][j]]++;
	}
	for (int i = n; i; i--) {
		int t = list[i];
		for (int j = 0; j < g[t].size(); j++) hash[color[g[t][j]]] = i;
		int j;
		for (j = 1; ; j++) if (hash[j] != i) break;
		color[t] = j;
		if (j > ans) ans = j;
	}
	printf("%d\n", ans);
	return 0;
}