Jerrycyx @ 2022-05-29 10:46:26
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 100005
#define M 1000005
using namespace std;
int n,m;
int x;
struct Allan{
int from,to;
int next;
}edge[M];
int tot=0;
int head[N];
int from[N],to[N];
int dfn[N],low[N];
int sta[N],top;
int num=0;
int scc[N],cnt=0;
int sum[N];
int deg[N];
int f[N],s[N];
int topcnt=0;
bool flag[N];
int d[N],a[N];
int out[N];
int ans1,ans2;
inline void add(int from,int to)
{
tot++;
edge[tot].from=from;
edge[tot].to=to;
edge[tot].next=head[from];
head[from]=tot;
deg[to]++;
out[from]++;
return;
}
inline void Get()
{
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from[i],&to[i]);
add(from[i],to[i]);
}
return;
}
void Tarjan(int x)
{
low[x]=dfn[x]=++num;
sta[++top]=x;
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(dfn[to]==0)
{
Tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(scc[to]==0)
low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x])
{
cnt++;
while(sta[top+1]!=x)
{
scc[sta[top]]=cnt;
sum[cnt]++;
top--;
}
}
return;
}
inline void Tarjan_All()
{
for(int i=1;i<=n;i++)
if(dfn[i]==0) Tarjan(i);
return;
}
inline bool cmp(Allan x,Allan y)
{
if(x.from==y.from) return x.to<y.to;
else return x.from<y.from;
}
void Rebuild()
{
for(int i=1;i<=m;i++)
{
edge[i].from=scc[edge[i].from];
edge[i].to=scc[edge[i].to];
}
sort(edge+1,edge+m+1,cmp);
memset(head,0,sizeof(head));
memset(deg,0,sizeof(deg));
memset(out,0,sizeof(out));
tot=0;
for(int i=1;i<=m;i++)
{
if(edge[i].from!=edge[i].to&&(edge[i].from!=edge[i-1].from||edge[i].to!=edge[i-1].to))
{
add(edge[i].from,edge[i].to);
}
}
m=tot;
return;
}
void Topsort()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
if(deg[i]==0)
{
f[i]=sum[i];
s[i]=1;
ans1=max(ans1,f[i]);
q.push(i);
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
deg[y]--;
if(deg[y]==0)
q.push(y);
if(f[x]+sum[y]>f[y])
{
f[y]=f[x]+sum[y];
ans1=max(ans1,f[y]);
s[y]=0;
}
if(f[x]+sum[y]==f[y])
s[y]=(s[y]+s[x])%(::x);
}
}
return;
}
inline void Print()
{
for(int i=1;i<=n;i++)
if(f[i]==ans1)
ans2=(ans2+s[i])%x;
printf("%d\n%d\n",ans1,ans2);
return;
}
int main()
{
Get();
Tarjan_All();
Rebuild();
Topsort();
Print();
return 0;
}
(::x
代表访问全局变量 x
)
by TernaryTree @ 2022-05-29 10:48:22
标题别用