@[liuenyin](/user/892979)
思路和[这篇题解](https://www.luogu.com.cn/blog/user21621/solution-p3119)有点像。
by liuenyin @ 2023-08-27 18:51:56
@[liuenyin](/user/892979)
新代码（改了几个地方，之前没O2全wa，现在开不开都是21pts
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define debug
typedef long long ll;
const int N=1e5+5;
const int M=1e5+5;
/*
思路:
Tarjan+topo
*/
vector<int> vec[N];//原图
//Tarjan配套
int scc_cnt;
int sccno[N];
int dfs_clock;
int dfn[N];
int low[N];
int scc_w[N];
stack<int> s;
//缩点配套
vector<int> G1[N];//正图
vector<int> G2[N];//反图
//拓扑配套
queue<int> q1;
queue<int> q2;
int f1[N];//f1[i] 从1到i的最长路
int f2[N];//f2[i] i->1最长路
int in1[N];//正图入度
int in2[N];//反着的
int n,m;
//tarjan
void dfs(int u){
dfs_clock++;
dfn[u]=low[u]=dfs_clock;
s.push(u);
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i];
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
//new scc
scc_cnt++;
int x=0,val=0;
do{
x=s.top();
sccno[x]=scc_cnt;
s.pop();
val++;
}while(x!=u);
scc_w[scc_cnt]=val;
}
}
void find_scc(){
memset(sccno,0,sizeof sccno);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(scc_w,0,sizeof scc_w);
dfs_clock=scc_cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i);
}
}
}
//缩点
void sd(){
for(int i=1;i<=n;i++){
for(int j=0;j<vec[i].size();j++){
int v=vec[i][j];
if(sccno[i]==sccno[v])continue;
G1[sccno[i]].push_back(sccno[v]);
in1[sccno[v]]++;
G2[sccno[v]].push_back(sccno[i]);
in2[sccno[i]]++;
}
}
}
void bfs1(){
f1[1]=scc_w[sccno[1]];
for(int i=1;i<=scc_cnt;i++){
if(!in1[i]){
q1.push(i);
}
}
while(!q1.empty()){
int tp=q1.front();
q1.pop();
for(int i=0;i<G1[tp].size();i++){
int v=G1[tp][i];
in1[v]--;
if(f1[tp]>0)f1[v]=max(f1[v],f1[tp]+scc_w[v]);
if(!in1[v]){
q1.push(v);
}
}
}
}
void bfs2(){
f2[1]=scc_w[sccno[1]];
for(int i=1;i<=scc_cnt;i++){
if(!in2[i]){
q2.push(i);
}
}
while(!q2.empty()){
int tp=q2.front();
q2.pop();
for(int i=0;i<G2[tp].size();i++){
int v=G2[tp][i];
in2[v]--;
if(f2[tp]>0)f2[v]=max(f2[v],f2[tp]+scc_w[v]);
if(!in2[v]){
q2.push(v);
}
}
}
}
//求max
int solve(){
int mx=scc_w[sccno[1]];
for(int i=1;i<=n;i++){
#ifdef debug
cout<<sccno[i]<<" "<<scc_w[sccno[i]]<<" "<<f1[sccno[i]]<<" "<<f2[sccno[i]]<<endl;
#endif
for(int j=0;j<vec[i].size();j++){
if(sccno[i]!=sccno[vec[i][j]] and f1[sccno[vec[i][j]]]>0 and f2[sccno[i]]>0)mx=max(mx,f1[sccno[vec[i][j]]]+f2[sccno[i]]-scc_w[sccno[1]]);
}
}
return mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
vec[x].push_back(y);
}
find_scc();
sd();
for(int i=1;i<=n+5;i++)f1[i]=f2[i]=-1e9;
bfs1();
bfs2();
cout<<solve();
return 0;
}
```
by liuenyin @ 2023-08-28 15:56:54
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int sj=100010;
int dfn[sj],low[sj],c[sj],jl[sj],dis[sj],s[sj];
int o[sj],h[sj],l[sj],w[sj];
int m,n,e1,e2,e3,cnt,ge,zh,ans;
bool r[sj];
struct B
{
int v,ne;
}b[sj];
struct BS
{
int u,to,nex;
}bs[sj];
struct BSS
{
int to,nex;
}bss[sj];
inline int re()
{
int jg=0,jk=0;
jk=getchar()-'0';
if(jk>=0&&jk<=9) jg+=jk;
jk=getchar()-'0';
while(jk>=0&&jk<=9)
{
jg*=10;
jg+=jk;
jk=getchar()-'0';
}
return jg;
}
void add(int x,int y)
{
b[e1].v=y;
b[e1].ne=h[x];
h[x]=e1++;
}
void ad2(int x,int y)
{
bs[e2].to=y;
bs[e2].nex=l[x];
bs[e2].u=x;
l[x]=e2++;
}
void ad3(int x,int y)
{
bss[e3].to=y;
bss[e3].nex=o[x];
o[x]=e3++;
}
void init()
{
n=re();
m=re();
memset(h,-1,sizeof(h));
memset(l,-1,sizeof(l));
memset(o,-1,sizeof(o));
int a1,a2;
for(int i=1;i<=m;i++)
{
a1=re();
a2=re();
add(a1,a2);
}
}
int bj(int x,int y)
{
return x<y?x:y;
}
void spfa1(int x)
{
dis[x]=w[x];
r[x]=1;
queue<int> q;
q.push(x);
int f;
while(!q.empty())
{
f=q.front();
for(int i=l[f];i!=-1;i=bs[i].nex)
{
if(dis[bs[i].to]<dis[f]+w[bs[i].to])
{
dis[bs[i].to]=dis[f]+w[bs[i].to];
if(r[bs[i].to]!=1)
{
q.push(bs[i].to);
r[bs[i].to]=1;
}
}
}
r[f]=0;
q.pop();
}
}
void spfa2(int x)
{
dis[x]=w[x];
r[x]=1;
queue<int> q;
q.push(x);
int f;
while(!q.empty())
{
f=q.front();
for(int i=o[f];i!=-1;i=bss[i].nex)
if(dis[bss[i].to]<dis[f]+w[bss[i].to])
{
dis[bss[i].to]=dis[f]+w[bss[i].to];
if(r[bss[i].to]!=1)
{
q.push(bss[i].to);
r[bss[i].to]=1;
}
}
r[f]=0;
q.pop();
}
}
void tarjan(int x)
{
dfn[x]=low[x]=++cnt;
s[++ge]=x;
r[x]=1;
for(int i=h[x];i!=-1;i=b[i].ne)
{
if(!dfn[b[i].v])
{
tarjan(b[i].v);
low[x]=bj(low[x],low[b[i].v]);
}
else if(r[b[i].v])
low[x]=bj(low[x],dfn[b[i].v]);
}
if(low[x]==dfn[x])
{
int li;
zh++;
do
{
li=s[ge--];
c[li]=zh;
w[zh]++;
r[li]=0;
}while(li!=x);
}
}
int db(int &x,int y)
{
x=x>y?x:y;
}
int main()
{
init();
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
for(int j=h[i];j!=-1;j=b[j].ne)
if(c[i]!=c[b[j].v])
{
ad2(c[i],c[b[j].v]);
ad3(c[b[j].v],c[i]);
}
memset(r,0,sizeof(r));
memset(dis,0,sizeof(dis));
spfa1(c[1]);
for(int i=1;i<=zh;i++)
jl[i]=dis[i];
memset(r,0,sizeof(r));
memset(dis,0,sizeof(dis));
spfa2(c[1]);
ans=1;
for(int i=0;i<e2;i++)
if(jl[bs[i].to]&&dis[bs[i].u])
db(ans,jl[bs[i].to]+dis[bs[i].u]-w[c[1]]);
printf("%d",ans);
return 0;
}
```
by chaizechen_czc @ 2023-08-31 19:29:41
@[liuenyin](/user/892979)
by chaizechen_czc @ 2023-08-31 19:30:11
@[chaizechen_czc](/user/877062) 感谢
by liuenyin @ 2023-09-05 18:49:05
@[chaizechen_czc](/user/877062) 不过您能看出来我代码中的问题吗？（已关
by liuenyin @ 2023-09-05 18:49:42
@[liuenyin](/user/892979) ok 没事了
by liuenyin @ 2023-09-05 19:37:43
经测试，是bfs初始条件炸了（感谢题解对拍
hack:
```
6 13
4 6
1 5
4 1
5 2
2 4
5 3
6 2
5 4
4 6
4 3
1 3
1 4
1 2
```
std out: `6`
my out: `10`
by liuenyin @ 2023-09-05 19:39:12
没事
by chaizechen_czc @ 2023-09-06 20:42:05