C++11(clang++ 3.9) 解法, 执行用时: 365ms, 内存消耗: 11872K, 提交时间: 2019-04-14 16:02:43

#include<cstdio>
#include<iostream>
#include<vector>
#include<iterator>

using namespace std;

typedef int int_t;
const int_t maxn = 10010;

vector<int_t> G[maxn];
bool vis[maxn];
int_t xl[maxn],deg[maxn];
int_t ccol[maxn];

template<class T>T read(T &x){
    x=0;char ch=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x;
}

int main(){
    int_t n = read(n),m = read(m);
    for(int_t i=1;i<=m;i++){
        int_t f = read(f),t = read(t);
        G[f].push_back(t);
        G[t].push_back(f);
    }
    for(int_t i=1;i<=n;i++){
        int_t p = 0;
        for(int_t j=1;j<=n;j++)
            if(!vis[j] && deg[j]>=deg[p])p = j;
        xl[i] = p;vis[p] = true;
        for(vector<int_t>::iterator it = G[p].begin();it != G[p].end();it ++)
            if(!vis[*it])++deg[*it];
    }    
    int_t ans = 0;
    for(int_t i=1;i<=n;i++)
        ans = max(ans,deg[i]+1);
    cout<<ans;
}