rt. 评测记录（不要在意乱码

（下载了 #2 的数据 但是 $m ≈ 10^5$...

有注释无乱码版本:

#include<bits/stdc++.h>
using namespace std;
//#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]--;
            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]--;
            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]])mx=max(mx,f1[sccno[vec[i][j]]]+f2[sccno[i]]-scc_w[sccno[1]]);
        }
    }
    return mx;
}

int 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();
    memset(f1,0xff,sizeof f1);//初始化成无穷小 
    memset(f2,0xff,sizeof f2);
    bfs1();
    bfs2();
    cout<<solve();
    return 0;
}