Input
第一行包含两个整数N,M,X。N,M分别表示图G的点数与边数,X的意义如上文所述。接下来M行,每行两个正整数a, b,表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。
Output
应包含两行,第一行包含一个整数K。第二行包含整数C Mod X.
把图缩点,然后跑一个最长路,拓扑就ok了
注意判重边
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m,p;
int x,y;
int tot=0;
int P=0;
struct NODE
{
int nex,to;
}nex[1000005];
NODE nex2[1000005];
int head[100005];
int dnf[100005];
int dfs_clock=0;
int sta[100005];
int low[100005];
int top=0;
int bel[100005];
int head2[100005];
int in[100005];
int size[100005];
int val[100005];
int cc[100005];
int ins[100005];
inline void add(int x,int y)
{
nex[++tot].to=y;
nex[tot].nex=head[x];
head[x]=tot;
}
void tarjan(int u){
dnf[u]=low[u]=++dfs_clock;sta[++top]=u;
for(int i=head[u];i;i=nex[i].nex)
{
if(in[nex[i].to]) continue;
if(!dnf[nex[i].to]) tarjan(nex[i].to);
low[u]=min(low[u],low[nex[i].to]);
}
if(low[u]==dnf[u]){
int v;P++;
do{
size[P]++;
bel[v=sta[top--]]=P;in[v]=1;
}while(u!=v);
}
}
inline void rbuild()
{
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=nex[j].nex)
{
int dmf=nex[j].to;
if(bel[i]!=bel[dmf])
{
nex2[++tot].to=bel[dmf];
nex2[tot].nex=head2[bel[i]];
head2[bel[i]]=tot;
ins[bel[dmf]]++;
}
}
}
int fa[100005];
void spfa()
{
queue<int> Q;
memset(in,0,sizeof(in));
for(int i=1;i<=P;i++)
{
if(ins[i]==0)
{
val[i]=size[i];
cc[i]=1;
Q.push(i);
in[i]=1;
}
}
while(!Q.empty()){
int tt=Q.front();
Q.pop();
for(int i=head2[tt];i;i=nex2[i].nex)
{
int dmf=nex2[i].to;
if(ins[dmf]&&!in[dmf])
{
ins[dmf]--;
if(ins[dmf]==0)
{
Q.push(dmf);
in[dmf]=1;
}
if(fa[dmf]==tt) continue;
if(val[tt]+size[dmf]>val[dmf])
{
val[dmf]=val[tt]+size[dmf];
cc[dmf]=cc[tt];
}
else if(val[tt]+size[dmf]==val[dmf]) cc[dmf]=(cc[dmf]+cc[tt])%p;
fa[dmf]=tt;
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++){
if(!dnf[i]) tarjan(i);
}
tot=0;
rbuild();
spfa();
int maxx=0;
for(int i=1;i<=P;i++)
{
maxx=max(maxx,val[i]);
}
printf("%d\n",maxx);
int ans=0;
for(int i=1;i<=P;i++)
if(val[i]==maxx)
(ans+=cc[i])%p;
printf("%d\n",ans%p);
return 0;
}