Plus_Ultra @ 2019-08-20 09:22:00
到底是哪儿错了。。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#define MAXN 1000010
using namespace std;
int edge[2*MAXN],nxt[2*MAXN],head[MAXN],tot,n,m,mod;
int dfn[MAXN],low[MAXN],scc[MAXN],in[MAXN],cnt,ti;
stack<int> S;
queue<int> q;
int x[MAXN],y[MAXN],b[MAXN],rdu[MAXN];
int dis[MAXN],ans,sum,e[MAXN];
void add(int x,int y)
{
edge[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++ti;
S.push(x);
for(int i=head[x];i;i=nxt[i])
{
int y=edge[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!scc[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x])
{
scc[x]=++cnt;in[cnt]++;
while(S.top()!=x)
{
int y=S.top();
scc[y]=cnt;
in[cnt]++;
S.pop();
}
S.pop();
}
}
bool cmp(int a,int l)
{
if(x[a]==x[l]) return y[a]<y[l];
return x[a]<x[l];
}
void pre()
{
for(int i=1;i<=m;i++)
b[i]=i,x[i]=scc[x[i]],y[i]=scc[y[i]];//???b[i]=i
sort(b+1,b+m+1,cmp);//x+1,x+m+1
}
void build()
{
tot=0;
memset(head,0,sizeof(head));
for(int k=1;k<=m;k++)
{
int i=b[k];//?
if(x[i]!=y[i]&&(x[i]!=x[b[k-1]]||y[i]!=y[b[k-1]]))//(x[i]!=x[i-1]||y[i]!=y[i-1])
add(x[i],y[i]),rdu[y[i]]++;
}
}
void topsort()
{
for(int i=1;i<=cnt;i++)
if(!rdu[i])
{
e[i]=1;
dis[i]=in[i];
q.push(i);
if(dis[ans]<dis[i]) ans=i;//?
}
while(q.size())
{
int x=q.front();
for(int i=head[x];i;i=nxt[i])
{
int y=edge[i];rdu[y]--;
if(dis[y]<dis[x]+in[y])//+in[x]
{
dis[y]=dis[x]+in[y];//+in[x]
e[y]=0;
if(dis[y]>dis[ans]) ans=y;
}
if(dis[y]==dis[x]+in[y])//+in[x]
{
e[y]=(e[y]+e[x])%mod;
if(!rdu[y]) q.push(y);//if(!(--rdu[y]))
}
}
}
}
int main()
{
cin>>n>>m>>mod;
for(int i=1;i<=m;i++)
{
cin>>x[i]>>y[i];
add(x[i],y[i]);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
pre();
build();
topsort();
for(int i=1;i<=n;i++)
if(dis[i]==dis[ans]) sum=(sum+e[i])%mod;
cout<<dis[ans]<<endl<<sum<<endl; //ans,sum
return 0;
}
by Plus_Ultra @ 2019-08-20 09:53:53
改了q.pop()后64分。。。
by Plus_Ultra @ 2019-08-20 10:22:39
结帖