BZOJ 5450 轰炸 (强连通缩点+DAG最长路)

#include <bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T&x){
    x=0;int f=1;char c=getchar();
    while(c<‘0‘ || c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); }
    while(c>=‘0‘ && c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); }
    x*=f;
}
#define REP(i,s,t) for(int i=s;i<=t;i++)
#define clr(a,b) memset(a,b,sizeof(a))
const int N = 1e6+5;
int n,m,cnt1,cnt2,tot,top,scc;
int head1[N],head2[N],dfn[N],low[N],bel[N],num[N],dp[N],instk[N],stk[N];

struct Edge{ int from,to,nxt; }e1[N],e2[N];

inline void add1(int u,int v){
    e1[++cnt1]=(Edge){ u,v,head1[u] };head1[u]=cnt1; 
}
inline void add2(int u,int v){
    e2[++cnt2]=(Edge){ u,v,head2[u] };head2[u]=cnt2;
}
void Tarjan(int u){
    dfn[u]=low[u]=++tot;
    instk[u]=1;stk[++top]=u;
    for(int i=head1[u];i;i=e1[i].nxt){
        int v=e1[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(instk[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scc;
        while(true){
            int v=stk[top--];
            instk[v]=0;
            bel[v]=scc;
            num[scc]++;     //统计每个强连通分量中的点数
            if(v==u)break;
        }
    }
}
inline void gao(){          //缩点之后正向建图
    // for(auto e:e1){
    for(int i=1;i<=cnt1;i++){
        Edge e=e1[i];
        int u=e.from,v=e.to;
        if(bel[u]!=bel[v])add2(bel[u],bel[v]);
    }
}
int DFS(int u){             //记忆化搜索求解DAG最长路
    if(dp[u])return dp[u];
    int ans=num[u];
    for(int i=head2[u];i;i=e2[i].nxt){
        int v=e2[i].to;
        ans=max(ans,DFS(v)+num[u]);
    }
    return dp[u]=ans;
}
int main(){
    read(n);read(m);
    REP(i,1,m){
        int u,v;read(u);read(v);
        add1(u,v);
    }
    REP(i,1,n) if(!dfn[i]) Tarjan(i);
    gao();
    DFS(1);
    int ans=-1;
    for(int i=1;i<=scc;i++){
        ans=max(ans,DFS(i));
    }
    printf("%d\n",ans);
}