莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 记住：tarjan 后的点是逆序的，明白 tarjan 算法的人都知道
2. tarjan 的好处：知道这个点是属于哪个连通块的，每个连通块的点的个数
3. 缩点后建立新的连通图
4. 拓扑序列求一遍最长路
5. 最后选出最大值即可

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = 2000010;

int n,m,mod;
int h[N],hs[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int f[N],g[N];

void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;

    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[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        } while(y!=u);
    }
}

int main()
{
    cin>>n>>m>>mod;

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(h,a,b);
    }

    //tarjan缩点
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    memset(hs,-1,sizeof hs);

    //建立拓扑序列的连通图
    unordered_set<LL> S;
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            LL hash=a*1000000ll+b;
            if(a!=b&&!S.count(hash))
            {
                add(hs,a,b);
                S.insert(hash);
            }
        }

    // tarjan 后的点是逆序的
    for(int i=scc_cnt;i;i--)
    {
        //一条新的路
        if(!f[i])
        {
            f[i]=sz[i];
            g[i]=1;
        }

        //求最长路
        for(int j=hs[i];~j;j=ne[j])
        {
            int k=e[j];
            if(f[k]<f[i]+sz[k])
            {
                f[k]=f[i]+sz[k];
                g[k]=g[i];
            }
            else if(f[k]==f[i]+sz[k]) g[k]=(g[k]+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<<'\n'<<sum<<endl;

    return 0;
}