萌新求助，一道水题

agicy @ 2019-01-24 20:21:36

by agicy @ 2019-01-24 20:22:08

代码在此：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
#define min(a,b) ( (a) < (b) ? (a) : (b) )

bool vis[100001];
int n,m,x;
int f[1000001],t[1000001],Edge_ID[1000001];
int cnt,head[100001],to[1000001],Next[1000001];
int dfn[100001],low[100001],time,Stack[100001],top;
int color[100001],Tarjan_cnt,Tarjan_num[100001];
int inDeg[100001];
int _head,_tail,Q[100001];
int ans,dis[100001],Way[100001];

void Rebuild(void);
void Topo_Init(void);
void Topo(void);
void Tarjan(int);
void Add_Edge(int,int);
bool sort_rule(int,int);

int main(void){
    register int i,sum=0;
    scanf("%d%d%d",&n,&m,&x);
    for(i=1;i<=m;++i){
        scanf("%d%d",&f[i],&t[i]);
        Add_Edge(f[i],t[i]);
    }
    for(i=1;i<=n;++i)
        if(!dfn[i])
            Tarjan(i);
    Rebuild();
    Topo_Init();
    Topo();
    for(i=1;i<=Tarjan_cnt;++i)
        if(dis[i]==dis[ans])
            sum=(sum+Way[i])%x;
    printf("%d\n%d\n",dis[ans],sum);
    return 0;
}

void Rebuild(void){
    register int i,ID;
    for(i=1;i<=m;++i){
        Edge_ID[i]=i;
        f[i]=color[f[i]];
        t[i]=color[t[i]];
    }
    sort(Edge_ID+1,Edge_ID+m+1,sort_rule);
    cnt=0;
    memset(head,0,sizeof(head));
    for(i=1;i<=m;++i){
        ID=Edge_ID[i];
        if(f[ID]!=t[ID]&&(f[ID]!=f[Edge_ID[i-1]]||t[ID]!=t[Edge_ID[i-1]])){
            ++inDeg[t[ID]];
            Add_Edge(f[ID],t[ID]);
        }
    }
    return;
}

void Topo_Init(void){
    register int i;
    for(i=1;i<=Tarjan_cnt;++i)
        if(!inDeg[i]){
            Q[_tail++]=i;
            dis[i]=Tarjan_num[i];
            Way[i]=1;
            if(dis[ans]<dis[i])
                ans=i;
        }
    return;
}

void Topo(void){
    register int i,ID,To;
    while(_head<_tail){
        ID=Q[_head++];
        for(i=head[ID];i;i=Next[i]){
            To=to[i];
            --inDeg[To];
            if(dis[To]<dis[ID]+Tarjan_num[To]){
                dis[To]=dis[ID]+Tarjan_num[To];
                Way[To]=0;
                if(dis[ans]<dis[To])
                    ans=To;
            }
            if(dis[To]==dis[ID]+Tarjan_num[To]){
                Way[To]=(Way[To]+Way[ID])%x;
                if(!inDeg[To])
                    Q[_tail++]=To;
            }
        }
    }
    return;
}

void Tarjan(int ID){
    register int i,To;
    vis[ID]=true;
    dfn[ID]=low[ID]=++time;
    Stack[++top]=ID;
    for(i=head[ID];i;i=Next[i]){
        To=to[i];
        if(!dfn[To]){
            Tarjan(To);
            low[ID]=min(low[ID],low[To]);
        }
        else if(vis[To])
            low[ID]=min(low[ID],dfn[To]);
        else
            continue;
    }
    if(dfn[ID]==low[ID]){
        ++Tarjan_cnt;
        do{
            To=Stack[top--];
            vis[To]=false;
            ++Tarjan_num[Tarjan_cnt];
            color[To]=Tarjan_cnt;
        }while(ID!=To);
    }
    return;
}

void Add_Edge(int f,int t){
    Next[++cnt]=head[f];
    to[cnt]=t;
    head[f]=cnt;
    return;
}

bool sort_rule(int a,int b){
    if(f[a]!=t[b])
        return f[a]<f[b];
    else
        return t[a]<t[b];
}

by Yoo_ @ 2019-01-24 20:23:14

@卢安来 昨天刚学Tarjan的蒟蒻路过

by Nova_守门员 @ 2019-01-24 20:27:12

震惊，一lg大佬认为紫题是水题！

像我这种菜鸡，刷题刷的超少，紫题都没动过几道，您真是TQL！

by agicy @ 2019-01-24 20:29:27

刚刚发现一个手抖的错误

bool sort_rule(int a,int b){
    if(f[a]!=/*这*/t[b]/**里/)//打错了
        return f[a]<f[b];
    else
        return t[a]<t[b];
}

改成

bool sort_rule(int a,int b){
    if(f[a]!=f[b])
        return f[a]<f[b];
    else
        return t[a]<t[b];
}

还是WA了3个点。

by Nova_守门员 @ 2019-01-24 20:29:47

Orz

by PCCP @ 2023-06-10 17:02:32

@agicy 膜拜学长，ORZ