#include < cstdio > #include < iostream > #define N 10001#define M 1000001 using namespace std;
bool vis[N];
int st[N],
top;
int color[N],
mark[N],
sa[N],
d[N];
int n,
m;
int tot,
front[N << 1],
to[M * 3],
nxt[M * 3];
void read(int & x) {
x = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
}
void add(int u, int v) {
to[++tot] = v;
nxt[tot] = front[u];
front[u] = tot;
}#define f(x) x + n + 1 void mcs() {
for (int i = 1; i <= n; i++) add(f(0), i);
int pos,
mx = 0;
for (int i = n; i; --i) {
pos = 0;
for (int j = front[f(mx)]; j && !pos; j = nxt[j]) if (!vis[to[j]]) {
pos = to[j];
vis[pos] = true;
sa[i] = pos;
} else front[f(mx)] = nxt[j];
if (!pos) mx--,
i++;
else {
for (int j = front[pos]; j; j = nxt[j]) if (!vis[to[j]]) {
d[to[j]]++;
add(f(d[to[j]]), to[j]);
mx = max(mx, d[to[j]]);
}
}
}
}
int main() {
read(n);
read(m);
int u,
v;
for (int i = 1; i <= m; ++i) {
read(u);
read(v);
add(u, v);
add(v, u);
}
mcs();
int ans = 0;
for (int i = n; i; --i) {
for (int j = front[sa[i]]; j; j = nxt[j]) mark[color[to[j]]] = i;
int j;
for (j = 1; j <= n && mark[j] == i; j++);
color[sa[i]] = j;
ans = max(ans, j);
}
printf("%d", ans);
}
来源: http://www.bubuko.com/infodetail-2287194.html