强联通缩点拓扑排序去重边小技巧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

inline long long read(){
    long long ans = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
        f *= (ch == '-') ? -1 : 1, ch = getchar();
    do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
    while(isdigit(ch));
    return ans * f;
}

const int MAXN = 100005, MAXM = 1000005;
struct Graph{
    int head[MAXN], last[MAXM], next[MAXM], lineNum;
    void add(int x,int y){
        lineNum++, next[lineNum] = head[x], last[lineNum] = y, head[x] = lineNum;
    }    
}G, G2;

int dfn[MAXN], low[MAXN], vis[MAXN], siz[MAXN], bel[MAXN], sta[MAXN], inch[MAXN], cnt = 0;
int Dp[MAXN], dep[MAXN];
queue<int> Q;
void tarjan(int x){
    dfn[x] = low[x] = ++dfn[0], sta[++sta[0]] = x, vis[x] = true;
    for(int l=G.head[x]; l; l=G.next[l]){
        int y = G.last[l];
        if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if(vis[y]) low[x] = min(low[x], dfn[y]);
    }
    if(low[x] == dfn[x]){
        cnt++;
        do bel[sta[sta[0]]] = cnt, vis[sta[sta[0]]] = false, siz[cnt]++;
        while(sta[sta[0]--] != x);
    }
}

int main(){
    int N = read(), M = read(), MOD = read();
    for(int i=1; i<=M; i++){
        int u = read(), v = read();
        G.add(u, v);
    }
    for(int i=1; i<=N; i++) if(!dfn[i])
        tarjan(i);
    for(int x=1; x<=N; x++) for(int l=G.head[x]; l; l=G.next[l]){
        int y = G.last[l];
        if(bel[x] != bel[y])
            G2.add(bel[x], bel[y]), inch[bel[y]]++;
    }
    for(int i=1; i<=cnt; i++) if(!inch[i])
        Q.push(i), dep[i] = siz[i], Dp[i] = 1;
    memset(vis, 0, sizeof(vis));
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        for(int l=G2.head[x]; l; l=G2.next[l]){
            int y = G2.last[l];
            inch[y]--;
            if(!inch[y]) Q.push(y);
            if(vis[y] == x) continue;
            vis[y] = x;
            if(dep[y] < dep[x] + siz[y])
                dep[y] = dep[x] + siz[y], Dp[y] = Dp[x];
            else if(dep[y] == dep[x] + siz[y])
                Dp[y] = (Dp[y] + Dp[x]) % MOD;
        }
    }
    int ans = 0, maxDep = 0;
    for(int i=1; i<=cnt; i++){
        if(maxDep < dep[i])
            maxDep = dep[i], ans = Dp[i];
        else if(maxDep == dep[i])
            ans = (ans + Dp[i]) % MOD;
    }
    printf("%d
%d", maxDep, ans);
    return 0;
}