(乱搞) $O(n^2log(n))$

看到n=5000，于是瞎搞了一阵，整了一个傻逼算法

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2*1e4+5;
int n,m,fa[N],cnt=1,h[N],nm,s[N],t[N],prt[N],v[N],f[N][20],d[N],D[N],vis[N];
struct node{
    int to,nxt,v;
}w[N*2];
void Add(int x,int y)
{
    cnt++;
    w[cnt].to=y;
    w[cnt].nxt=h[x];
    w[cnt].v=1;
    h[x]=cnt;
}
void Dfs(int x,int p)
{
    f[x][0]=p;d[x]=d[p]+1;
    for(int j=1;j<=log(n)/log(2);j++)
        if(f[x][j-1])f[x][j]=f[f[x][j-1]][j-1];
    for(int i=h[x];i;i=w[i].nxt)
    {
        int y=w[i].to;
        if(y==p)continue;
        prt[y]=i;
        Dfs(y,x);
    }
}
int Lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    int k=log(d[x])/log(2)+1;
    for(int i=k;i>=0;i--)if(f[x][i]&&d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=k;i>=0;i--)if(f[x][i]&&f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int Getfa(int x)
{
    return x==fa[x]?x:fa[x]=Getfa(fa[x]);
}
void Erase(int x,int y)
{
    int lca=Lca(x,y);
    while(x!=lca){w[prt[x]].v=w[prt[x]^1].v=0;vis[prt[x]]=vis[prt[x]^1]=1;x=f[x][0];}
    while(y!=lca){w[prt[y]].v=w[prt[y]^1].v=0;vis[prt[y]]=vis[prt[y]^1]=1;y=f[y][0];}
}
int Bfs(int x)
{
    for(int i=1;i<=n;i++)D[i]=1e9;
    D[x]=0;
    queue<int>q;
    q.push(x);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=w[i].nxt)
        {
            int y=w[i].to;
            if(D[y]==1e9)D[y]=D[x]+w[i].v,q.push(y);
        }
    }
    int k=1;
    for(int i=2;i<=n;i++)if(D[i]>D[k])k=i;
    return k;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(Getfa(x)!=Getfa(y))Add(x,y),Add(y,x),fa[Getfa(y)]=Getfa(x);
        else s[++nm]=x,t[nm]=y;
    }
    Dfs(1,0);
    for(int i=1;i<=nm;i++)Erase(s[i],t[i]);
    int ans=0;
    for(;;ans++){
        int r1=Bfs(1);
        int r2=Bfs(r1);
        if(!D[r2]){
            printf("%d\n",ans);
            return 0;
        }
        Erase(r1,r2);
    }
}