思路是 Tarjan 缩点完之后跑分层图 spfa,但它死循环了
找不出哪里写挂了
#include<bits/stdc++.h>
#define endl '\n'
#define ri register
#define int long long
#define inf 2147483647
#define pb(x) push_back((x))
#define mp(x,y) make_pair((x),(y))
#define reset(x,y) memset((x),(y),sizeof((x)))
using namespace std;
inline int read()
{
int x=0,f=0;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
return f?-x:x;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int N=2e5+10;
int Head[N],Next[N],To[N],Cnt,head[N],next[N],to[N],cnt;
inline void Add(int x,int y) {Next[++Cnt]=Head[x];Head[x]=Cnt;To[Cnt]=y;}
//原图连边
inline void add(int x,int y) {next[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
//分层图连边
int n,m,id,sum,x[N],y[N],dfn[N],low[N],siz[N],num[N],dis[N];
//num[x]表示x这个点在第几个强连通分量内,siz是该点的点权
stack<int> st;
bool vis[N];
inline void Tarjan(int x)
{
dfn[x]=low[x]=++id;vis[x]=1;st.push(x);
for(ri int i=Head[x];i;i=Next[i])
{
ri int y=To[i];
if(!dfn[y]) Tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
ri int y;++sum;
do y=st.top(),st.pop(),vis[y]=0,num[y]=sum,++siz[sum]; while(x!=y);
}
}//Tarjan板子
inline void Spfa(int s)
{
queue<int> q;reset(vis,0);q.push(s);vis[s]=1;
while(!q.empty())
{
ri int x=q.front();q.pop();vis[x]=0;
for(ri int i=head[x];i;i=next[i])
{
ri int y=to[i];
if(dis[y]<dis[x]+siz[x])
{
dis[y]=dis[x]+siz[x];
// if((double)clock()/CLOCKS_PER_SEC>0.95) {cout<<dis[num[1]+sum];exit(0);}
if(!vis[y]) q.push(y),vis[y]=1;
}
}
}
}//spfa求最长路
signed main()
{
n=read();m=read();
for(ri int i=1;i<=m;++i)
x[i]=read(),y[i]=read(),Add(x[i],y[i]);
for(ri int i=1;i<=n;++i)
if(!dfn[i]) Tarjan(i);
for(ri int i=1;i<=sum;++i)
siz[i+sum]=siz[i];
add(num[1],num[1]+sum);
for(ri int i=1;i<=m;++i)
if(num[x[i]]!=num[y[i]]) add(num[x[i]],num[y[i]]),add(num[y[i]],num[x[i]]+sum),add(num[x[i]]+sum,num[y[i]]+sum);
Spfa(num[1]);
cout<<dis[num[1]+sum];
return 0;
}