WA 24pts求调

就是一个裸tarjan+topsort

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int n,m,ans,mcnt,mod,cnt[N];
int h[N],e[N],ne[N],idx;
int scc_cnt,id[N],s[N],timestamp;
int dfn[N],low[N],q[N],f[N],stk[N],tt,d[N];
bool in_stk[N];
vector<int> g[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    in_stk[u]=true;stk[++tt]=u;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u]){
        ++scc_cnt;
        int y;
        do{
            y=stk[tt--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            s[scc_cnt]++;
        }while(y!=u);
    }
}
void topsort(){
    int hh=0;tt=-1;
    for(int i=1;i<=scc_cnt;i++)
        if(!d[i]){
            q[++tt]=i;
            f[i]=s[i];
            cnt[i]=1;
            ans=max(ans,f[i]);
        }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=0;i<g[t].size();i++){
            int j=g[t][i];
            if(f[j]<f[t]+1){
                cnt[j]=cnt[t];
                f[j]=f[t]+1;
            }
            else if(f[j]==f[t]+1) cnt[j]=(cnt[j]+cnt[t])%mod;
            ans=max(ans,f[j]);
            if(--d[j]==0) q[++tt]=j;
        }
    }
}
signed main(){
    memset(h,-1,sizeof(h));
    scanf("%lld%lld%lld",&n,&m,&mod);
    while(m--){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int now=1;now<=n;now++)
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            if(id[j]!=id[now]){
                g[id[now]].push_back(id[j]);
                d[id[j]]++;
            }
        }
    topsort();
    for(int i=1;i<=scc_cnt;i++)
        if(f[i]==ans) mcnt=(mcnt+cnt[i])%mod; 
    printf("%lld\n%lld",ans,mcnt);
    return 0;
}