蒟蒻好紧张啊 蒟蒻好紧张啊 蒟蒻好紧张啊 蒟蒻好紧张啊

一开始方向好像走错了 乱推了个拓扑的式子 然后FST了

然后还不肯放弃 挣扎了20分钟 又受到了刚上来都打完球了的ldx的diss

"我靠，这么傻逼的题你还没A吗"

好吧的确是傻逼题

先缩点

设s是1所在的scc的编号

考虑逆行的使用姿势

对于一个可以从s出发到达的点 逆行到一个可以到达s的点

然后这个东西你可以跑正反两发spfa

最后枚举每个点 枚举出边 ans=max(ans,dis[i][1]+dis[vis][2]-num[s]);

注意是遍历反向边的数组

// luogu-judger-enable-o2#include
    
     #define N 100005using namespace std;template
     
      inline void read(T &x){    x=0; int f=1;    static char ch=getchar();    while((!isdigit(ch)&&ch!='-'))  ch=getchar();    if(ch=='-') f=-1,ch=getchar();    while(isdigit(ch))  x=x*10+ch-'0',ch=getchar();    x*=f;}int n,m,tot,first[N];struct Edge{    int to,next;}edge[2*N];inline void addedge(int x,int y){    tot++;    edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot;}int dfn[N],low[N],sign,cnt,belong[N],num[N];stack 
      
        sta;bool insta[N];void dfs(int now){    dfn[now]=low[now]=++sign;    insta[now]=true;    sta.push(now);    for(int u=first[now];u;u=edge[u].next)    {        int vis=edge[u].to;        if(!dfn[vis])        {            dfs(vis);            low[now]=min(low[vis],low[now]);        }        else if(insta[vis]) low[now]=min(dfn[vis],low[now]);    }    if(dfn[now]==low[now])    {        int temp;        cnt++;        do        {            temp=sta.top();            num[cnt]++;            belong[temp]=cnt;            insta[temp]=false;            sta.pop();        }while(temp!=now);    }}bool inque[N];vector 
       
         res1[N],res2[N];int s,dis[N][3];void spfa(int f,vector 
        
          *res){    queue 
         
           q; q.push(s); memset(inque,0,sizeof(inque)); dis[s][f]=num[s]; while(!q.empty()) { int now=q.front(); inque[now]=false; q.pop(); for(int i=0;i
          
           dis[vis][f]) { dis[vis][f]=dis[now][f]+num[vis]; if(!inque[vis]) q.push(vis),inque[vis]=true; } } }}int main(){ read(n); read(m); for(int i=1,x,y;i<=m;i++) { read(x),read(y); addedge(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); for(int i=1;i<=n;i++) { for(int u=first[i];u;u=edge[u].next) { int vis=edge[u].to; if(belong[i]!=belong[vis]) { res1[belong[i]].push_back(belong[vis]); res2[belong[vis]].push_back(belong[i]); } } } s=belong[1]; spfa(1,res1); spfa(2,res2); int ans=num[s]; for(int i=1;i<=cnt;i++) { if(dis[i][1]==0) continue; for(int j=0;j