哎，这道题打了半个小时，调了两个小时，最后发现竟然是把 \(Tarjan\) 里 \(while\) 给打成 \(if\) ,呜呜，枉费我两个小时时间，所以下次一定要记住不能打成 \(if\) （估计也就我一个人吧）
题意
定义最大半连通图：对于图中任意两点 \(u,v\) ,存在一条 \(u\) 到 \(v\) 的有向路径 或者 从 \(v\) 到 \(u\) 的有向路径。求一个图中不同的最大半连通子图的大小和数目。
看到题目时应该很容易想到，如果两点互相可以到达，那么它们必是半连通图，所以考虑先 \(Tarjan\) 缩点，缩完点后，删去重边，图就成为 \(DAG\),然后我们只要对这个图求一个最长链的长度和条数，就可以用拓扑进行 \(dp\) 了
设 \(dis_i\) 表示到 \(i\) 这个点的最长链长度， \(S_i\) 表示到 \(i\) 的最长链的条数， \(val_i\) 表示缩完点后，\(i\) 这个强连通分量的大小，很容易想到转移方程:
\(1. dis_i > dis_j+val_i ,dis_i = dis_j+val_i,S_i=S_j.\)
\(2. dis_i == dis_j + val_i ,S_i+=S_j.\)
最后答案就是 \(ans1=max(dis_i)\) 和 \(ans2=\sum_{i=1}^{cnt}{S_i(dis_i==ans1)}.\)
一些小建议
\(1.S_i\) 要边加边模，防止炸掉。
\(2. Tarjan\) 缩点后的点的排列顺序是逆拓扑序，所以不需要对新图进行拓扑排序 ,直接倒序做就行。
\(3.\) 要判重边，不然会死得很惨。
\(code\)
#include<bits/stdc++.h>
#define N 1000005
#define M 10000005
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,mod,tot,t,cnt,dis[N],maxn,ss,top;
int dfn[N],low[N],s[N],vis[N],gp[N];
int Head[N],to[M],Next[M],val[N],S[N],pre[N];
map<pair<int,int>,bool> H;
void add(int u,int v){to[++tot]=v,pre[tot]=u,Next[tot]=Head[u],Head[u]=tot;}
void tarjan(int x){
dfn[x]=low[x]=++t,vis[x]=1,s[++top]=x;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int k=s[top--];cnt++;
while(x!=k){
gp[k]=cnt,val[cnt]++,vis[k]=0;
k=s[top--];
}
gp[x]=cnt,val[cnt]++,vis[x]=0,dis[cnt]=val[cnt],S[cnt]=1;
}
}
int main(){
n=read(),m=read(),mod=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();add(u,v);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
m=tot;
tot=0,memset(Head,0,sizeof(Head));
for(int i=1;i<=m;++i){
int x=gp[pre[i]],y=gp[to[i]];
if(x==y) continue;
if(!H[make_pair(x,y)])
add(x,y),H[make_pair(x,y)]=1;
}
for(int x=cnt;x;--x){
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(dis[y]<dis[x]+val[y]) dis[y]=dis[x]+val[y],S[y]=S[x];
else if(dis[y]==dis[x]+val[y]) S[y]=(S[y]+S[x])%mod;
}
}
for(int i=1;i<=cnt;++i){
if(dis[i]>maxn) maxn=dis[i],ss=S[i];
else if(dis[i]==maxn) ss+=S[i],ss%=mod;
}
printf("%d\n%d\n",maxn,ss);
return 0;
}