第一行包含三个正整数 $n, m, x$ ($n \leq 10^5, m \leq 10^6, x \leq 10^8$)，$n, m$ 分别表示图 $G$ 的点数与边数，$X$ 的意义如上文所述。
接下来 $m$ 行，每行两个正整数 $a, b$，表示一条有向边 $(a, b)$。图中的每个点将编号为 $1, 2, 3, \cdots, n$，保证输入中同一个 $(a, b)$ 不会出现两次。
输出两行，第一行包含一个整数 $K$。第二行包含整数 $C \bmod X$。
"半连通" 的意思即两点 $u, v$ 要么 $u \to v$ 有通路，要么 $v \to u$ 有通路。那么如果 $u, v$ 是强连通的，则它们一定是半连通的。
那么对于某一个强连通分量，如果其中有一个点在某个半连通子图内，则这个强连通分量中的所有点都可以加入并且依然满足 "半连通" 的性质。
于是原图中，每个强连通分量作为一个整体，因此可以进行 (Tarjan) 缩点。考虑一个有向无环图，它的半连通子图中，任意两个点肯定是按照拓扑序连通。
于是就可以 DP 了，记 $f_i$ 表示到 (缩点后) 点 $i$ 为止的 (带权) 最大半连通子图的大小。则对于点 $i$，设连接到点 $i$ 的点的集合为 $N^+(i)$，点 $i$ 的权值 (对应的强连通分量的大小) 为 $w_i$，则 $$ f_i = \left( \max_{k \in N^+(i)} f_k \right) + w_i $$
最后所有 $f_i$ 的最大值即为所求 (注意图可能是不连通的)。接下来是最大半连通子图的个数，可以参考这道题。即令 $g_i$ 表示到点 $i$ 为止的大小为 $f_i$ 的半连通子图的个数，则对 $f_k + w_i > f_i$ 的 $k$，令 $g_i \gets g_k$；对 $f_k + w_i = f_i$ 的 $k$，只需要 $g_i \gets g_i + g_k$。
最后只需把满足 $f_k = \max f_i$ 的 $k$ 所对应的 $g_k$ 相加就是答案，时间复杂度 $O(n + m)$。
#include <bits/stdc++.h>
#define N 100034
#define M 1024404
using namespace std;
struct edge{
int u, v;
edge (int u0 = 0, int v0 = 0): u(u0), v(v0) {}
}e[M];
int mod;
int V, E, Es;
int u, v, i;
int first[N], next[M]; // adj
int cnt = 0, id[N], low[N]; // tarjan
int stc = 0, sta[N], in_stack[N]; // stack
int scc = 0, bel[N], top[N]; // shrink
int deg[N], size[N], que[N]; // toposort
int f[N], g[N], hash[N]; // dp
int ans, Count;
inline void up(int &x, const int y) {x < y ? x = y : 0;}
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline void add(int &x, const int y) {(x += y) >= mod ? x -= mod : 0;}
inline void addedge(int u, int v) {e[++Es] = edge(u, v); next[Es] = first[u]; first[u] = Es;}
void tarjan(int x){
int i, y;
id[x] = low[x] = ++cnt; in_stack[x] = 1; sta[stc++] = x;
for(i = first[x]; i; i = next[i])
if(!id[y = e[i].v]){
tarjan(y); down(low[x], low[y]);
}else if(in_stack[y]){
down(low[x], id[y]);
}
if(id[x] == low[x])
for(top[++scc] = x, y = 0; y != x; ){
y = sta[--stc]; in_stack[y] = 0; bel[y] = scc; ++size[scc];
}
}
void topo_sort_dp(){
int h, t = 0, x, y, i;
for(i = 1; i <= scc; ++i)
if(!deg[i]) {que[t++] = i; f[i] = size[i]; g[i] = 1;}
for(h = 0; h < t; ++h)
for(i = first[x = que[h]]; i; i = next[i]){
if(!--deg[y = e[i].v]) que[t++] = y;
if(hash[y] != x){
hash[y] = x;
if(f[x] + size[y] > f[y]){
f[y] = f[x] + size[y]; g[y] = g[x];
}else if(f[x] + size[y] == f[y])
add(g[y], g[x]);
}
}
}
int main(){
scanf("%d%d%d", &V, &E, &mod);
for(i = 1; i <= E; ++i){
scanf("%d%d", &u, &v);
addedge(u, v);
}
for(i = 1; i <= V; ++i) if(!id[i]) tarjan(i);
Es = 0; memset(first, 0, sizeof first);
for(i = 1; i <= E; ++i)
if((e[i].u = bel[e[i].u]) != (e[i].v = bel[e[i].v])){
addedge(e[i].u, e[i].v);
++deg[e[i].v];
}
topo_sort_dp();
for(i = 1; i <= scc; ++i) up(ans, f[i]);
for(i = 1; i <= scc; ++i) if(f[i] == ans) add(Count, g[i]);
printf("%d\n%d\n", ans, Count);
return 0;
}
坑1：这题汇聚了多个模板 (Tarjan; 缩点; 拓扑排序)，因此各个模板需要背熟练。
坑2：注意缩点后的图可能有重边，因此在 DP 的时候注意去重，避免一个 $g_k$ 更新多次。