sunqihuan @ 2024-12-12 22:25:38
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,dfn[N],low[N],scc,top,num,st[N],inst[N],belong[N],number[N],dp[N],cnt[N],du[N],mod;
vector<int> g[N],gg[N];
void tarjan(int u){
dfn[u]=low[u]=++num;
st[++top]=u;
inst[u]=0;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(dfn[v]==0){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(inst[v]==1){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
scc++;
int now;
do{
now=st[top--];
inst[now]=0;
belong[now]=scc;
number[scc]++;
}while(now!=u);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>mod;
for(int i=1;i<=n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(dfn[i]==0)tarjan(i);
}
set<int> S;
for(int i=1;i<=n;i++){
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
int s1=belong[i],s2=belong[v];
int hash=s1*1000000ll+s2;
if(s1!=s2 && !S.count(hash)){
gg[s1].push_back(s2);
S.insert(hash);
}
}
}
for(int i=scc;i>=1;i--){
if(!dp[i]){
dp[i]=number[i];
cnt[i]=1;
}
for(int j=0;j<gg[i].size();j++){
int v=g[i][j];
if(dp[v]<dp[i]+number[v]){
dp[v]=dp[i]+number[v];
cnt[v]=cnt[i];
}else if(dp[v]==dp[i]+number[v]){
cnt[v]=(cnt[v]+cnt[i])%mod;
}
}
}
int maxn=0,sum=0;
for(int i=1;i<=scc;i++){
if(dp[i]>maxn){
maxn=dp[i];
sum=cnt[i];
}else if(dp[i]==maxn)sum=(sum+cnt[i])%mod;
}
cout<<maxn<<endl<<sum;
return 0;
}
输出错误