C++14(g++5.4) 解法, 执行用时: 352ms, 内存消耗: 30784K, 提交时间: 2020-01-06 21:08:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=2e5+1;
int n,m,low[maxn],dfn[maxn],a[maxn],b[maxn],vis[maxn]={0},mx=0,id;
ll num[maxn],cnt=0,sum=0;
stack<int>s;
vector<int>g[maxn],G[maxn];
ll quick(ll a,ll b){
    ll ans=1;  
    a=a%mod;
    while(b!=0){
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
void tarjan(int x,int fa)
{
	low[x]=dfn[x]=++cnt;
	vis[x]=1;
	s.push(x);
	int flag=0;
	for(int to:g[x])
	{
		if(fa==to) 
		{
			if(++flag<2) continue;
		}
		if(!dfn[to]) tarjan(to,x),low[x]=min(low[x],low[to]);
		else if(vis[to]) low[x]=min(low[x],low[to]);
	}
	if(dfn[x]==low[x])
	{
		int t;
		++sum;
		do{
			t=s.top();
			num[t]=sum;
			vis[t]=0;
			s.pop();
		}while(t!=x);
	}
}
void dfs(int x,int fa,int deep)
{
	if(deep>mx) 
	{
		mx=deep;
		id=x;
	}
	for(int to:G[x]) {
		if(to==fa) continue;
		dfs(to,x,deep+1);
	}
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
    	int u,v;
    	scanf("%d %d",&u,&v);
    	g[u].push_back(v);
    	g[v].push_back(u);
    	a[i]=u;b[i]=v;
	}
	tarjan(1,0);
	for(int i=1;i<=m;++i)
	if(num[a[i]]!=num[b[i]]) G[num[a[i]]].push_back(num[b[i]]),G[num[b[i]]].push_back(num[a[i]]);
	dfs(1,0,1);
	dfs(id,0,1);
	printf("%lld\n",1ll*(sum-mx)*quick(m+1,mod-2)%mod);
 } 

C++11(clang++ 3.9) 解法, 执行用时: 295ms, 内存消耗: 35452K, 提交时间: 2020-07-30 19:15:53

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int s=0,t,mx=-1,dfn[200005],low[200005],tot=0;
vector<int>R[200005],A[200005],B[200005];
long long fastpow(long long a,int b)
{
	long long s=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
	return s;
}
void tarjan(int x,int fa)
{
    int i,j,flag=1;
    dfn[x]=low[x]=++tot;
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(j==fa&&flag){flag=0;continue;}
        if(!dfn[j])
        {
            tarjan(j,x);
            low[x]=min(low[x],low[j]);
            A[x].push_back(j),A[j].push_back(x);
            if(low[j]>dfn[x])s++,B[x].push_back(1),B[j].push_back(1);
			else B[x].push_back(0),B[j].push_back(0);
        }
        else low[x]=min(low[x],dfn[j]);
    }
}
void DFS(int x,int fa,int val)
{
	int i,j;
	if(mx<val)mx=val,t=x;
	for(i=0;i<A[x].size();i++)
	{
		j=A[x][i];
		if(j!=fa)DFS(j,x,val+B[x][i]);
	}
}
int main()
{
	int i,j,k,n,m;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&j,&k);
		R[j].push_back(k),R[k].push_back(j);
	}
	tarjan(1,0);
	DFS(1,0,0),DFS(t,0,0);
	printf("%d\n",(s-mx)*fastpow(m+1,mod-2)%mod);
    return 0;
}