经典的tarjan,但是这次要求个数,因此考虑做完后先重建边,去掉重边,因为缩点后每个连通块是一个点,所以往外的点都是同一个。
之后在拓扑序里面求一下就行。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10,M=2e6+10; int f[N],h[N],ne[M],e[M],idx; int scnt,cnt[N],ins[N],in[N]; stack<int> q; int id[N],dfn[N],low[N]; int times; int hs[N]; int g[N]; void add(int h[],int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int n,m,x; void tarjan(int u){ dfn[u]=low[u]=++times; q.push(u),ins[u]=1; int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(!dfn[j]){ tarjan(j); low[u]=min(low[u],low[j]); } else if(ins[j]){ low[u]=min(low[u],dfn[j]); } } if(dfn[u]==low[u]){ ++scnt; while(1){ int t=q.top(); q.pop(); ins[t]=0; id[t]=scnt; cnt[scnt]++; if(t==u) break; } } } set<ll> s; int main(){ cin>>n>>m>>x; int i; memset(h,-1,sizeof h); memset(hs,-1,sizeof hs); for(i=1;i<=m;i++){ int a,b; scanf("%d%d",&a,&b); add(h,a,b); } for(i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(i=1;i<=n;i++){ for(int j=h[i];j!=-1;j=ne[j]){ int k=e[j]; int a=id[i],b=id[k]; ll ha=100000ll*a+b; if(a!=b&&!s.count(ha)){ add(hs,a,b); s.insert(ha); } } } long long ans=0; long long sum=0; for(i=scnt;i;i--){ if(!f[i]){ f[i]=cnt[i]; g[i]=1; } for(int j=hs[i];j!=-1;j=ne[j]){ int k=e[j]; if(f[k]<f[i]+cnt[k]){ f[k]=f[i]+cnt[k]; g[k]=g[i]; } else if(f[k]==f[i]+cnt[k]){ g[k]=(g[k]+g[i])%x; } } } for(i=1;i<=scnt;i++){ if(ans<f[i]){ ans=f[i]; sum=g[i]; } else if(ans==f[i]){ sum=(sum+g[i])%x; } } cout<<ans<<endl; cout<<sum<<endl; }