Xing_ke @ 2020-03-25 00:19:02
#include<bits/stdc++.h>
#define M 1000005
using namespace std;
int n,m,mod;
struct Node{
int fr,to,nxt;
}e[M];
int cnt=0,head[M];
void add1(int fr,int to){
cnt++;
e[cnt].fr=fr;
e[cnt].to=to;
e[cnt].nxt=head[fr];
head[fr]=cnt;
}
struct node{
int fr,to,nxt;
}e2[M];
int cntt=0,head2[M];
void add2(int fr,int to){
cntt++;
e2[cntt].fr=fr;
e2[cntt].to=to;
e2[cntt].nxt=head2[fr];
head2[fr]=cntt;
}
int t=0,gg=0;
stack<int> s;
int id[M],sz[M];
int dfn[M],low[M];
void taj(int x){
dfn[x]=low[x]=++t; s.push(x);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
taj(y);
low[x]=min(low[x],low[y]);
}else if(!id[y]){
low[x]=min(low[x],dfn[y]);
}
} int u;
if(low[x]==dfn[x]){
gg++;
do{
u=s.top();s.pop();
id[u]=gg;sz[gg]++;
}while(x!=u);
}
}
int us[M];
int f[M],g[M];
void topu(){
for(int x=1;x<=n;++x){
f[x]=sz[x];
g[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(id[x]==id[y]) continue;
add2(id[x],id[y]);
}
}
for(int x=gg;x>=1;x--){
for(int i=head2[x];i;e2[i].nxt){
int y=e2[i].to;
if(us[y]==x) continue;//<——here!!
us[y]=x;
if(f[y]<f[x]+sz[y]){
f[y]=f[x]+sz[y];
g[y]=g[x];
}else if(f[y]==f[x]+sz[y]){
g[y]+=g[x];
g[y]%=mod;
}
}
}
}
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int ans=0,tmp=0;
int main(){
n=read(),m=read(),mod=read();
for(int i=1;i<=m;++i){
int x=read(),y=read();
add1(x,y);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) taj(i);
topu();
for(int i=1;i<=gg;++i){
if(f[i]>ans){
ans=f[i];
tmp=g[i];
}else if(f[i]==ans){
tmp+=g[i];
tmp%=mod;
}
}
printf("%d\n%d\n",ans,tmp);
return 0;
}
借鉴题解xiaofulll dalao的(第一页 ヾ(◍°∇°◍)ノ゙
加油,祝你全家健康>wQ
谢谢啦~
by Xing_ke @ 2020-03-25 00:19:32
静坐
by Xing_ke @ 2020-03-25 00:20:07
先下线了,dalao找到了@我下~
by Kinandra @ 2020-03-25 07:42:37
应该是 i=e2[i].nxt 吧
by Kinandra @ 2020-03-25 07:43:02
凌晨发帖可真行
by Xing_ke @ 2020-03-25 12:33:41
蟹蟹蟹蟹~
by Xing_ke @ 2020-03-25 12:34:51
不凌晨没办法(菜是原罪QWQ