思路：$tarjan+DP$
提交：1次
题解：首先对于一个强连通分量一定是一个半连通分量，并且形成的半连通分量的大小一定是它的$size$,所以我们先缩点。
这样，我们相当于要在新的$DAG$上找一个最长链（一旦有分叉边就不可能是一个半连通分量）。
于是乎写了个$dfs$,$sz[u]$表示这个（缩完后的）点的包含点的数量，$mx[u]$表示以$u$为起点最长链的长度，$tot[u]$表示方案数。
但是注意这个图有可能不连通。
#include<cstdio> #include<iostream> #include<map> #define ull unsigned long long #define ll long long #define R register int using namespace std; #define pause (for(R i=1;i<=10000000000;++i)) #define In freopen("NOIPAK++.in","r",stdin) #define Out freopen("out.out","w",stdout) namespace Fread { static char B[1<<15],*S=B,*D=B; #ifndef JACK #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++) #endif inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } inline bool isempty(const char& ch) {return (ch<=36||ch>=127);} inline void gs(char* s) { register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar())); } } using Fread::g; using Fread::gs; namespace Luitaryi { const int N=100010,M=1000010; map<pair<int,int>,bool> mp; int n,m,mod; int vr[M<<1],nxt[M<<1],fir[M<<1],cnt; inline void add(int u,int v) {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;} int vv[M<<1],nn[M<<1],ff[M<<1],ct; inline void adde(int u,int v) {vv[++ct]=v,nn[ct]=ff[u],ff[u]=ct;} int dfn[N],low[N],c[N],stk[N],sz[N],t[N],num,cc,top; bool vis[N]; inline void tarjan(int u) { dfn[u]=low[u]=++num; stk[++top]=u,vis[u]=true; for(R i=fir[u];i;i=nxt[i]) { R v=vr[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { ++cc; R tmp; do tmp=stk[top],--top,c[tmp]=cc,++sz[cc],vis[tmp]=false; while(tmp!=u); } } int anss,ans,mx[N],tot[N]; inline void dfs(int u) { vis[u]=true; mx[u]=sz[u],tot[u]=1; for(R i=ff[u];i;i=nn[i]) { R v=vv[i]; if(!vis[v]) dfs(v); if(sz[u]+mx[v]>mx[u]) { mx[u]=sz[u]+mx[v]; tot[u]=tot[v]; } else if(sz[u]+mx[v]==mx[u]) tot[u]=(tot[u]+tot[v])%mod; } ans=max(mx[u],ans); } inline void main() { n=g(),m=g(),mod=g(); for(R i=1,u,v;i<=m;++i) u=g(),v=g(),add(u,v); for(R i=1;i<=n;++i) if(!dfn[i]) tarjan(i); for(R u=1;u<=n;++u) for(R i=fir[u];i;i=nxt[i]) { R v=vr[i]; if(c[u]!=c[v]&&mp.find(make_pair(c[u],c[v]))==mp.end()) ++t[c[v]],adde(c[u],c[v]),mp[make_pair(c[u],c[v])]=true; } for(R i=1;i<=cc;++i) if(!t[i]||!vis[i]) dfs(i); for(R i=1;i<=cc;++i) if(mx[i]==ans) anss=(anss+tot[i])%mod; printf("%d %d ",ans,anss); } } signed main() { Luitaryi::main(); return 0; }
2019.07.22