Mosher @ 2019-09-03 15:41:18
第七个点,会输出0,0;
貌似在统计入度时,最后结果没有为0的
tarjan缩点下来没问题,应该问题出在build中,是我map用法有误吗???
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
const ll maxn=4e5+5;
const ll maxm=2e6+5;
map<pair<ll,ll>,bool>mapp;
queue<ll>q;
ll dfn[maxn],low[maxn],dfs_clock,size,tot,head[maxn],n,m,col[maxn],dp[maxn],mod,sz[maxn],x[maxn],y[maxn],rd[maxn],dis[maxn],cnt[maxn],ans_id,ans;
struct node{
ll v,nxt;
}e[maxm];
il ll read(){
ll x=0;char a=getchar();
while(!isdigit(a)) a=getchar();
while(isdigit(a)) {x=x*10+a-'0';a=getchar();}
return x;
}
il void add(ll u,ll v){
e[++size].v=v;
e[size].nxt=head[u];
head[u]=size;
}
stack<ll>s;
void tarjan(ll u){
s.push(u);
dfn[u]=low[u]=++dfs_clock;
for(ll i=head[u];i;i=e[i].nxt){
ll v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!col[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
ll k;++tot;
do{
k=s.top();s.pop();
col[k]=tot;
sz[tot]++;
}while(k!=u);
}
}
il void clear(){
size=0;
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
}
il void build(){
for(ll i=1;i<=m;++i){
int nx=col[x[i]],ny=col[y[i]];
if(nx!=ny&&!mapp[make_pair(nx,ny)]){
rd[ny]++;
mapp[make_pair(nx,ny)]=1;
add(nx,ny);
}
}
}
void bfs(){
while(!q.empty()){
ll u=q.front();q.pop();
for(ll i=head[u];i;i=e[i].nxt){
ll v=e[i].v;
--rd[v];
if(dis[v]<dis[u]+sz[v]){
dis[v]=dis[u]+sz[v];
cnt[v]=0;
if(dis[ans_id]<dis[v]) ans_id=v;
}
if(dis[v]==dis[u]+sz[v]) cnt[v]=(cnt[v]+cnt[u])%mod;
if(!rd[v]) q.push(v);
}
}
}
int main(){
n=read();m=read();mod=read();
for(ll i=1;i<=m;++i){
x[i]=read();y[i]=read();
add(x[i],y[i]);
}
for(ll i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
clear();
build();
for(ll i=1;i<=tot;++i){
if(!rd[i]){
q.push(i);
dis[i]=sz[i];
cnt[i]=1;
if(dis[ans_id]<dis[i]) ans_id=i;
}
}
bfs();
for(ll i=1;i<=n;++i)
if(dis[i]==dis[ans_id]) ans=(ans+cnt[i])%mod;
printf("%lld\n%lld",dis[ans_id],ans);
}
by Mosher @ 2019-09-03 16:01:47
此贴终结
提个醒:空间要开足够大,比如乘10倍的亚子
by Peter0721 @ 2019-09-03 17:48:57
撤离ing