最大半联通子图对应缩点后的$DAG$上的最长链
复杂度$O(n + m)$
#include#include #include using namespace std;extern inline char gc() { static char RR[23456], *S = RR + 23333, *T = RR + 23333; if(S == T) fread(RR, 1, 23333, stdin), S = RR; return *S ++;}inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; }#define ri register int#define sid 1005000int 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] = 1; #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] = 0; 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 = 1, to = 0; for(ri i = 1; i <= nid; i ++) { if(!deg[i]) q[++ to] = i; f[i] = { cnt[i], 1 }; } #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 = { 0, 0 }; for(ri i = 1; 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 = 1; i <= m; i ++) { int u = read(), v = read(); addedge(u, v); } for(ri i = 1; i <= n; i ++) if(!dfn[i]) tarjan(i, 0); memset(cap, 0, (n + 2) << 2); memset(deg, 0, (n + 2) << 2); int cno = cnp; cnp = 0; for(ri i = 1; i <= cno; i ++) if(b[pre[i]] != b[node[i]]) addedge(b[pre[i]], b[node[i]]); top_dp(); return 0;}