tarjan缩点找出拓扑图中的最长链

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

typedef long long LL;

const int N=100005;
const int M=2000005;
const LL P=1000007; // hash code

int n, m, mod;
int h[N], hs[N], E=0; // 图和导出图
int dfn[N], low[N], ts=0;
bool vis[N];
stack<int> st;
int id[N], scc_cnt=0, sz[N]; // scc 数组
int f[N], g[N];

struct Edge{
    int v, ne;
}e[M];

void add(int h[], int a, int b){ // 建图, 根据参数不同建立普通图或者导出图
    e[E].v=b;
    e[E].ne=h[a];
    h[a]=E++;
}

void tarjan(int u){
    dfn[u]=low[u]=ts++;
    st.push(u); vis[u]=true;
    for(int i=h[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){ // 树枝边
            tarjan(v);
            low[u]=min(low[u], low[v]);
        }
        else if(vis[v]){ // 横叉边或者后向边
            low[u]=min(low[u], dfn[v]);
        }
    }
    if(dfn[u]==low[u]){ // 当前节点为scc起点
        ++scc_cnt;
        int j;
        do{
            j=st.top(); st.pop(); vis[j]=false; id[j]=scc_cnt; sz[scc_cnt]++;
        }while(j!=u);
    }
}

int main(){
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    cin>>n>>m>>mod;
    while(m--){
        int a, b;
        cin>>a>>b;
        add(h, a, b);
    }

    // 找出所有scc
    for(int i=1; i<=n; ++i)
        if(!dfn[i]) tarjan(i);

    // 缩点建立导出图
    unordered_set<LL> rec;
    for(int i=1; i<=n; ++i){
        for(int j=h[i]; ~j; j=e[j].ne){
            int v=e[j].v;
            int a=id[i], b=id[v];
            LL hash=a*P+b;
            if(a!=b && !rec.count(hash)){
                add(hs, a, b);
                rec.insert(hash);
            }
        }
    }

    for(int i=scc_cnt; i; --i){
        if(!f[i]){
            f[i]=sz[i];
            g[i]=1;
        }
        for(int j=hs[i]; ~j; j=e[j].ne){
            int v=e[j].v;
            if(f[v]<f[i]+sz[v]){
                f[v]=f[i]+sz[v];
                g[v]=g[i];
            }
            else if(f[v]==f[i]+sz[v]) g[v]=(g[v]+g[i])%mod;
        }
    }

    int maxf=0, sum=0;
    for(int i=1; i<=scc_cnt; ++i){
        if(f[i]>maxf){maxf=f[i]; sum=g[i];}
        else if(f[i]==maxf) sum=(sum+g[i])%mod;
    }
    cout<<maxf<<endl;
    cout<<sum<<endl;

    return 0;
}