可耐的菊花茶 @ 2018-07-05 09:16:04
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define maxe 1000005
using namespace std;
bool vis[maxn];
int n,e,tt,tim,tot,top,ans,sum,x[maxe],y[maxe],lnk[maxn],net[maxe],son[maxe];
int que[maxn],fa[maxn],ru[maxn],siz[maxn],col[maxn],stack[maxn],dfn[maxn],low[maxn],f[maxn],g[maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline int add(int x,int y){net[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;}
void tarjan(int x){
dfn[x]=low[x]=++tim;
vis[x]=1;stack[++top]=x;
for (int j=lnk[x];j;j=net[j])
if (!dfn[son[j]]) tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
else if (vis[son[j]]) low[x]=min(low[x],dfn[son[j]]);
if (dfn[x]==low[x]){
col[0]++;
int sum=0,now=0;
while (now!=x){
sum++;
now=stack[top--];
col[now]=col[0];
vis[now]=0;
}
siz[col[0]]=sum;
}
}
inline int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void mrk_e(){
tot=0;
memset(lnk,0,sizeof(lnk));
for (int i=1;i<=col[0];i++) fa[i]=i;
for (int i=1;i<=e;i++)
if (col[x[i]]!=col[y[i]]){
int fx=get(col[x[i]]),fy=get(col[y[i]]);
if (fx==fy) continue;
fa[fx]=fy;ru[col[y[i]]]++;
add(col[x[i]],col[y[i]]);
}
}
void tuopu(){
int hed=0,tal=0;
for (int i=1;i<=col[0];i++){
f[i]=siz[i];g[i]=1;
if (!ru[i]) que[++tal]=i;
}
while (hed!=tal){
hed++;
int x=que[hed];
for (int j=lnk[x];j;j=net[j]){
ru[son[j]]--;
if (ru[son[j]]==0) que[++tal]=son[j];
if (f[son[j]]<f[x]+siz[son[j]]) f[son[j]]=f[x]+siz[son[j]],g[son[j]]=g[x];
else if (f[son[j]]==f[x]+siz[son[j]]) g[son[j]]=(g[son[j]]+g[x])%tt;
}
}
}
int main(){
freopen("1093.in","r",stdin);
freopen("1093.out","w",stdout);
n=read();e=read();tt=read();
for (int i=1;i<=e;i++){
x[i]=read(),y[i]=read();
add(x[i],y[i]);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
mrk_e();
tuopu();
for (int i=1;i<=col[0];i++)
if (f[i]>ans) ans=f[i],sum=g[i];
else if (f[i]==ans) sum=(sum+g[i])%tt;
printf("%d\n%d\n",ans,sum);
return 0;
}
by 可耐的菊花茶 @ 2018-07-05 09:18:28
好尴尬,一不小心,dalao成了dolao。。。
by creed_ @ 2018-07-12 00:13:23
@可耐的菊花茶 这个题很坑,要注意缩点以后会出现重边,然后你再dp的时候就炸掉了。。。。。
by 可耐的菊花茶 @ 2018-07-12 08:06:00
@creed_ 可我mrk_e里面用并查集拿来判重边了啊。
by creed_ @ 2018-07-12 08:24:25
@可耐的菊花茶
并查集判重边应该是不可以的
1 2 1 3 2 4 3 4
你考虑这样一个图
前三条边加进去,3和4就已经在一个集合了
但第四条边确实也还有加的必要对吧。
所以还是排序判重好了
by creed_ @ 2018-07-12 08:24:56
@可耐的菊花茶
1 2
1 3
2 4
3 4
by 可耐的菊花茶 @ 2018-07-12 09:48:55
@creed_ 仿佛明白了什么,谢谢dalao。