bzoj1093 [ZJOI2007]最大半联通子图 缩点 + 拓扑序

最大半联通子图对应缩点后的$DAG$上的最长链

复杂度$O(n + m)$

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

extern inline char gc() {

    static char RR[], *S = RR + , *T = RR + ;

    if(S == T) fread(RR, , , stdin), S = RR;

    return *S ++;

}

inline int read() {

    int p = , w = ; char c = gc();

    while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }

    while(c >= '' && c <= '') p = p *  + c - '', c = gc();

    return p * w;

}

#define ri register int

#define sid 1005000

int n, m, id, nid, cnp, mod, top;

int pre[sid], nxt[sid], node[sid], cap[sid], vis[sid];

int low[sid], dfn[sid], st[sid], ins[sid], cnt[sid], b[sid], deg[sid], q[sid];

inline void addedge(int u, int v) {

    nxt[++ cnp] = cap[u]; cap[u] = cnp;

    pre[cnp] = u; node[cnp] = v; deg[v] ++;

}

void tarjan(int o, int fa) {

    low[o] = dfn[o] = ++ id; st[++ top] = o; ins[o] = ;

    #define cur node[i]

    for(int i = cap[o]; i; i = nxt[i]) {

        if(!dfn[cur]) tarjan(cur, o), low[o] = min(low[o], low[cur]);

        else if(ins[cur]) low[o] = min(low[o], dfn[cur]);

    }

    if(dfn[o] == low[o]) {

        int p; ++ nid;

        do{ p = st[top --]; b[p] = nid;

            ins[p] = ; cnt[nid] ++;

        } while(p != o);

    }

}

inline void inc(int &a, int b)

{ a += b; if(a >= mod) a -= mod; }

struct dp {

    int sz, num;

    friend void cmax(dp &a, dp b) {

        if(b.sz > a.sz) a = b;

        else if(b.sz == a.sz) inc(a.num, b.num);

    }

} f[sid];

void top_dp() {

    int fr = , to = ;

    for(ri i = ; i <= nid; i ++) {

        if(!deg[i]) q[++ to] = i;

        f[i] = { cnt[i],  };

    }

    #define cur node[i]

    while(fr <= to) {

        int o = q[fr ++];

        for(ri i = cap[o]; i; i = nxt[i]) {

            deg[cur] --; if(!deg[cur]) q[++ to] = cur;

            if(vis[cur] == o) continue;

            cmax(f[cur], (dp){ f[o].sz + cnt[cur], f[o].num } );

            vis[cur] = o;

        }

    }

    dp ans = { ,  };

    for(ri i = ; i <= nid; i ++) cmax(ans, f[i]);

    printf("%d\n%d\n", ans.sz, ans.num);

}

int main() {

    n = read(); m = read(); mod = read();

    for(ri i = ; i <= m; i ++) {

        int u = read(), v = read();

        addedge(u, v);

    }

    for(ri i = ; i <= n; i ++)

    if(!dfn[i]) tarjan(i, );

    memset(cap, , (n + ) << );

    memset(deg, , (n + ) << );

    int cno = cnp; cnp = ;

    for(ri i = ; i <= cno; i ++)

    if(b[pre[i]] != b[node[i]]) addedge(b[pre[i]], b[node[i]]);

    top_dp();

    return ;

}