题解

把所有起点入队，正向BFS，求出所有起点到每个点的路径数f[i]；

把终点入队，反向BFS，求出终点到每个点的路径数g[i]；

ans=max{g[u]*f[v]} | (u,v)∈E；

#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5001,M=50001;
int v[M],next[M],head[N],in[N],k;
int x[M],y[M],f[N],g[N],*d,q[N],n,m;
void add(int x,int y)
{
	v[++k]=y;next[k]=head[x];head[x]=k;
	in[y]++;
}
void bfs(int d[])
{
	memset(d,0,sizeof(d));
	int l=0,r=0;
	for(int i=1;i<=n;i++)
		if(!in[i])	q[++r]=i,d[i]=1;
	while(++l<=r)
		for(int i=head[q[l]];i;i=next[i])
		{
			d[v[i]]+=d[q[l]];
			if(!--in[v[i]])	q[++r]=v[i];
		}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		if(x>y)	swap(x[i],y[i]);
		add(x[i],y[i]);
	}
	bfs(f);
	memset(in,0,sizeof(in));
	memset(head,0,sizeof(head));k=0;
	for(int i=0;i<m;i++)	add(y[i],x[i]);
	bfs(g);
	int ans=0;
	for(int i=0;i<m;i++)
		ans=max(ans,f[x[i]]*g[y[i]]);
	printf("%d\n",ans);
}