Hydra_Shouko @ 2019-03-21 18:01:33

by Hydra_Shouko @ 2019-03-21 18:02:02

#include<bits/stdc++.h>
#define MAXN 100050
#define MAXM 1000050

using namespace std;

int low[MAXN],dfn[MAXN],sta[MAXN],rd[MAXN];
int tp,cnt,num;
bool ins[MAXN];
queue<int> q;
long long siz[MAXN];
int col[MAXN];
long long f[MAXN],g[MAXN];
int n,m;
long long p;

struct Edge{
    int to,nxt;
}edge[MAXM];
int head[MAXN],ectr;
void addedge(int from,int to){
    ectr++;
    edge[ectr].to = to;
    edge[ectr].nxt = head[from];
    head[from] = ectr;
}

struct Data{
    int a,b;
}data[MAXM];
struct DATA{
    int a,b;
}DA[MAXM]; 
bool cmp(DATA x,DATA y){
    if(x.a != y.a) return x.a<y.a;
    else return x.b<y.b;
}

void tarjan(int x){
    dfn[x] = low[x] = ++num;
    sta[++tp] = x;
    ins[x] = true;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }
        else if (ins[y]){
            low[x] = min(low[x] ,dfn[y]);
        }
    }
    if(dfn[x] == low[x] ){
        ++cnt;
        int y=0;
        do{
            y=sta[tp--];
            col[y] = cnt;
            siz[cnt] ++;
            ins[y] = false;
        }while (y!=x);
    }
}

void topo(){
    for(int i=1;i<=cnt;i++){
        if( !rd[i] ) q.push(i),f[i] = siz[i],g[i]=1;
    }
    while (!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=edge[i].nxt){
            int y=edge[i].to;
            if(!--rd[y]) q.push(y);
            if(f[x] + siz[y] > f[y] ){
                f[y] = siz[y] + f[x];
                g[y] = g[x];
                g[y] %=p;
            }
            else if(f[x] + siz[y] == f[y]){
                g[y] += g[x] ;
                g[y] %= p;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    cin>>p;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&data[i].a,&data[i].b);
        addedge(data[i].a,data[i].b);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++) head[i] = 0;
    ectr=0;
    for(int i=1;i<=m;i++){
        int x= col[data[i].a];
        int y= col[data[i].b];
        if(x==y) continue;
        DA[i].a=x;
        DA[i].b=y;
    }
    sort (DA +1,DA+1+m,cmp);
    int prex=0,prey=0;
    for(int i=1;i<=m;i++){
        int x=DA[i].a;
        int y=DA[i].b;
        if(x==prex && y==prey) continue;
        if(x!=y) addedge(x,y),rd[y]++,prex=x,prey=y;
    }
    topo();
    long long ans1=0,ans2=0;
    for(int i=1;i<=cnt;i++){
        ans1=max(ans1,f[i]);
    }   
    for(int i=1;i<=cnt;i++){
        if(f[i]==ans1){
            ans2+=g[i];
        }
    }
    cout<<ans1<<endl<<ans2;
    return 0;
}

by hongzy @ 2019-03-30 14:28:19

@SIN_XIII 您是不是漏取模了

by orzws @ 2021-10-18 21:48:48

@Hydra_Shouko 取模要在中间一直取