题目大意
约翰有(n)块草场，编号(1)到(n)，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。
贝西总是从(1)号草场出发，最后回到(1)号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。
(n,mle 10^5)
QwQ一开始看这个题 没有思路呀
首先一定是(tarjan)消环，对吧
我们可以考虑，如果只能反向走一条边，那我们可以枚举这个边呀，然后算一算(ans)
那么对于一条边(u->v)，如果我们选择反向走，我们能获得的收益是(val[v]+valn[u]-sval[1]) 其中(val[x])表示从1到x的最大收益，(valn[x])表示(x)到1的最大收益（这个可以通过建反图来算）
之所以减去(sval[1])，因为1这个联通快的贡献会算两边，按照题意，应该只算一遍。
为什么这样是对，为什么可以保证没有别的点的贡献被算两遍。
我们可以这么考虑，假设存在一个联通快他的贡献被计算了两次，那么他一定能到1，也能从1到，那么就说明存在环，但是因为我们在一开始(tarjan)缩点过，所以不会存在这么一个点，所以这样计算贡献是没有错的
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 1e5+1e2;
const int maxm = 1e6+1e2;
int point[maxn],nxt[maxm],to[maxm],sval[maxn];
int s[maxn],top;
int bel[maxn],roo[maxn];
int tot;
int cnt;
int n,m;
int x[maxm],y[maxm];
int low[maxn],dfn[maxn];
int vis[maxn],scc;
void addedge(int x,int y)
{
nxt[++cnt]=point[x];
to[cnt]=y;
point[x]=cnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s[++top]=x;
vis[x]=1;
for (int i=point[x];i;i=nxt[i])
{
int p = to [i];
if (!dfn[p])
{
tarjan(p);
low[x]=min(low[x],low[p]);
}
else
if(vis[p]) low[x]=min(low[x],dfn[p]);
}
if (low[x]==dfn[x])
{
scc++;
while (s[top+1]!=x)
{
//++scc;
bel[s[top]]=scc;
roo[s[top]]=x;
sval[scc]++;
vis[s[top]]=0;
top--;
}
}
}
int num[maxm];
int dis[maxn],disn[maxn];
queue<int> q;
void spfa(int s)
{
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[s]=1;
dis[s]=sval[bel[s]];
q.push(s);
while (!q.empty()){
int x = q.front();
q.pop();
vis[x]=0;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (dis[p]<dis[x]+sval[bel[p]])
{
dis[p]=dis[x]+sval[bel[p]];
if (!vis[p])
{
vis[p]=1;
q.push(p);
}
}
}
}
}
void spfa1(int s)
{
memset(disn,0,sizeof(disn));
memset(vis,0,sizeof(vis));
vis[s]=1;
disn[s]=sval[bel[s]];
q.push(s);
while (!q.empty()){
int x = q.front();
q.pop();
vis[x]=0;
for (int i=point[x];i;i=nxt[i])
{
int p = to[i];
if (disn[p]<disn[x]+sval[bel[p]])
{
disn[p]=disn[x]+sval[bel[p]];
if (!vis[p])
{
vis[p]=1;
q.push(p);
}
}
}
}
}
int main()
{
n=read(),m=read();
for (int i=1;i<=m;i++) {
x[i]=read(),y[i]=read();
addedge(x[i],y[i]);
}
for (int i=1;i<=n;i++)
{
if (!dfn[i]) tarjan(i);
}
//for (int i=1;i<=n;i++) cout<<sval[i]<<endl;
memset(point,0,sizeof(point));
cnt=0;
for (int i=1;i<=m;i++)
{
if (bel[x[i]]!=bel[y[i]])
{
addedge(roo[x[i]],roo[y[i]]);
num[i]=1;
}
}
spfa(roo[1]);
memset(point,0,sizeof(point));
cnt=0;
for (int i=1;i<=m;i++)
{
if (num[i]) addedge(roo[y[i]],roo[x[i]]);
}
spfa1(roo[1]);
int ans=0;
//for (int i=1;i<=n;i++) cout<<dis[i]<<" "<<disn[i]<<endl;
for (int i=1;i<=m;i++)
{
if (!num[i]) continue;
if (dis[roo[y[i]]] && disn[roo[x[i]]])
ans=max(ans,dis[roo[y[i]]]+disn[roo[x[i]]]-sval[bel[roo[1]]]);
}
cout<<ans;
return 0;
}