原题链接
题目的意思就是说找到最长路径的长度及数量。
显然，我们首先要tarjan缩点，然后建立新图，但要注意的是不能有重边，因为会影响我们计算数量，那我们可以用map记录一下两点是否有连边，然后我们进行拓扑求答案即可。
#include<bits/stdc++.h>
using namespace std;
#define il inline
const int maxn=1e6+5;
const int maxm=5e6+5;
map<pair<int,int>,bool>mapp;//pair，记录连边有无
queue<int>q;
int dfn[maxn],low[maxn],dfs_clock,size,tot,head[maxn],n,m,col[maxn],dp[maxn],mod,sz[maxn],x[maxn],y[maxn],rd[maxn],dis[maxn],cnt[maxn],ans_id,ans;
struct node{
int v,nxt;
}e[maxm];
il int read(){
int x=0;char a=getchar();
while(!isdigit(a)) a=getchar();
while(isdigit(a)) {x=x*10+a-'0';a=getchar();}
return x;
}
il void add(int u,int v){
e[++size].v=v;
e[size].nxt=head[u];
head[u]=size;
}
stack<int>s;
void tarjan(int u){ //缩点
s.push(u);
dfn[u]=low[u]=++dfs_clock;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!col[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int k;++tot;
do{
k=s.top();s.pop();
col[k]=tot;
sz[tot]++;
}while(k!=u);
}
}
il void clear(){
size=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
}
il void build(){
for(int i=1;i<=m;++i){
int nx=col[x[i]],ny=col[y[i]];
if(nx!=ny&&!mapp[make_pair(nx,ny)]){//map去重，未连边就连起来
rd[ny]++;//统计入度，为拓扑排序准备
mapp[make_pair(nx,ny)]=1;
add(nx,ny);
}
}
}
void bfs(){
while(!q.empty()){
int u=q.front();q.pop();//取出队列前端
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
--rd[v];
if(dis[v]<dis[u]+sz[v]){
dis[v]=dis[u]+sz[v];
cnt[v]=0;//路径数重新计算,清0的话，是因为下方累加
if(dis[ans_id]<dis[v]) ans_id=v;//下标更新
}
if(dis[v]==dis[u]+sz[v]) cnt[v]=(cnt[v]+cnt[u])%mod;//累加
if(!rd[v]) q.push(v);
}
}
}
int main(){
freopen("semi5.in","r",stdin);
n=read();m=read();mod=read();
for(int i=1;i<=m;++i){
x[i]=read();y[i]=read();
add(x[i],y[i]);//存下来，二次利用
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
clear();
build();
for(int i=1;i<=tot;++i){
if(!rd[i]){//从入度为0点，所跑出的最长链，一定比不从其跑的长，显然。
q.push(i);
dis[i]=sz[i];//更新
cnt[i]=1;
if(dis[ans_id]<dis[i]) ans_id=i;
}
}
bfs();
for(int i=1;i<=n;++i)
if(dis[i]==dis[ans_id]) ans=(ans+cnt[i])%mod;
printf("%d\n%d",dis[ans_id],ans);
}