Tarjan缩点+拓扑排序
attention：注意判断新图中的重边
先用Tarjan缩点，处理出每个分量的大小。
然后建个新图，设叶子节点的方案数为1，蓝后跑一遍拓扑排序即可。
code：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cctype> using namespace std; template <typename T> inline T min(T &a,T &b) {return a<b ?a:b;} template <typename T> inline T max(T &a,T &b) {return a>b ?a:b;} template <typename T> inline void read(T &x){ char c=getchar(); x=0; bool f=1; while(!isdigit(c)) f= !f||c=='-' ? 0:1,c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); x= f ? x:-x; } template <typename T> inline void output(T x){ if(!x) {putchar(48); return ;} if(x<0) putchar('-'),x=-x; int wt[50],l=0; while(x) wt[++l]=x%10,x/=10; while(l) putchar(wt[l--]+48); } struct data{ int f,t; bool operator < (const data &tmp) const{return f<tmp.f||(f==tmp.f&&t<tmp.t);} bool operator != (const data &tmp) const{return f!=tmp.f||t!=tmp.t;} }a[1000002]; int n,m,mod,d[100002],ted; long long f[100002],ans; int dfs_clock,dfn[100002],low[100002],_top,st[100002],tot,be[100002],val[100002]; int cnt1,hd1[100002],nxt1[1000002],ed1[100002],poi1[1000002]; int cnt2,hd2[100002],nxt2[1000002],ed2[100002],poi2[1000002],_in[100002]; int rts,rt[100002],mxd; queue <int> h; inline void add1(int x,int y){ nxt1[ed1[x]]=++cnt1; hd1[x]= hd1[x] ? hd1[x]:cnt1; ed1[x]=cnt1; poi1[cnt1]=y; } inline void add2(int x,int y){ nxt2[ed2[x]]=++cnt2; hd2[x]= hd2[x] ? hd2[x]:cnt2; ed2[x]=cnt2; poi2[cnt2]=y; ++_in[y]; } inline void tarjan(int x){ dfn[x]=low[x]=++dfs_clock; st[++_top]=x; for(int i=hd1[x];i;i=nxt1[i]){ if(!dfn[poi1[i]]) tarjan(poi1[i]),low[x]=min(low[x],low[poi1[i]]); else if(!be[poi1[i]]) low[x]=min(low[x],dfn[poi1[i]]); } if(low[x]==dfn[x]){ be[x]=++tot; ++val[tot]; while(st[_top]!=x) be[st[_top--]]=tot,++val[tot]; --_top; } } void find(){ //拓扑排序 for(int i=1;i<=tot;++i) if(!_in[i]) h.push(i),d[i]=val[i],f[i]=1; while(!h.empty()){ int x=h.front(); h.pop(); if(!hd2[x]) {rt[++rts]=x; mxd=max(mxd,d[x]); continue;} for(int i=hd2[x];i;i=nxt2[i]){ if(d[poi2[i]]<d[x]+val[poi2[i]]){ //如果深度更大就重新结算 d[poi2[i]]=d[x]+val[poi2[i]]; f[poi2[i]]=f[x]%mod; }else if(d[poi2[i]]==d[x]+val[poi2[i]]){ f[poi2[i]]=(f[poi2[i]]+f[x])%mod; } if((--_in[poi2[i]])==0) h.push(poi2[i]); } } } int main(){ read(n); read(m); read(mod); int q1,q2; for(int i=1;i<=m;++i) read(q1),read(q2),add1(q1,q2); for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;++i) for(int j=hd1[i];j;j=nxt1[j]) if(be[i]!=be[poi1[j]]) a[++ted]=(data){be[i],be[poi1[j]]}; sort(a+1,a+ted+1); for(int i=1;i<=ted;++i) //把重边判掉 if(a[i]!=a[i-1]) add2(a[i].f,a[i].t); find(); for(int i=1;i<=rts;++i) if(d[rt[i]]==mxd) ans=(ans+f[rt[i]])%mod; //深度最大的累加起来 output(mxd); putchar(' '); output(ans); return 0; }