LINK

先缩点,在$DAG$上跑最长路可以得到$dis[v]$

表示$1$号点的联通分量到$v$连通分量最多走多少草坪

当走到$u$点时使用反向机会走到点$v$,其中$v$一定是能到达点$1$所属的连通分量的

所以以$1$所在联通分量为起点,终点分别跑一次最长路

然后枚举那个中转点计算答案即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int inf = 1e9;
struct edge{
	int u,to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = ( edge ){u,v,head[u]},head[u] = cnt; }
int n,m,low[maxn],dfn[maxn],id,scc,stac[maxn],top,vis[maxn],sd[maxn],num[maxn];
void tarjan(int u)
{
	low[u] = dfn[u] = ++id; vis[u] = 1; stac[++top] = u;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( !dfn[v] )
		{
			tarjan(v);
			low[u] = min( low[u],low[v] );
		}
		else if( vis[v] )	low[u] = min( low[u],low[v] );
	}
	if( dfn[u]==low[u] )
	{
		int temp; scc++;
		while( temp = stac[top--] )
		{
			sd[temp] = scc; num[scc]++; vis[temp] = 0;
			if( temp==u )	break;
		}
	}
}
vector<int>vec1[maxn],vec2[maxn];
int dis1[maxn],dis2[maxn];
void spfa(int s,int dis[],vector<int>vec[] )
{
	queue<int>q;
	for(int i=1;i<=scc;i++)		dis[i] = -inf, vis[i] = 0;
	q.push( s ); dis[s] = num[s]; vis[s] = 1;
	while( !q.empty() )
	{
		int u = q.front(); q.pop();
		vis[u] = 0;
		for(auto v:vec[u] )
		{
			if( dis[u]+num[v]>dis[v] )
			{
				dis[v] = dis[u]+num[v];
				if( !vis[v] )	q.push( v ), vis[v] = 1;
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int l,r; cin >> l >> r;
		add(l,r);
	}
	for(int i=1;i<=n;i++)	if( !dfn[i] )	tarjan(i);
	for(int i=2;i<=cnt;i++)
	{
		int u = d[i].u, v = d[i].to;
		if( sd[u]!=sd[v] )
		{
			vec1[sd[u]].push_back( sd[v] );
			vec2[sd[v]].push_back( sd[u] );
		}
	}
	spfa( sd[1],dis1,vec1 ); spfa( sd[1],dis2,vec2 );
	int ans = num[sd[1]];
	for(int i=1;i<=n;i++)
	{
		int u = sd[i];
		for(auto v:vec2[u] )
			ans = max( ans,dis1[u]+dis2[v]-num[sd[1]] );
	}
	cout << ans;
}