【最大半连通子图——tarjan求最大连通分量，拓扑排序，树形DP】

题目

分析

最大连通分量肯定是满足半连通分量的要求，因此tarjan。

同时为了简化图，我们进行缩点，图一定变为拓扑图。

我们很容易看出，只要是一条不分叉的链，是满足条件的。

于是我们按照拓扑序不断树形DP

建边注意一下：

代码 #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5+10; const int M = 2e6+10; //要建两次图，第二次取决于第一次图中强连通分量的个数，最坏情况下为1e6 int dfn[N], sz[N], id[N], low[N], tot, cnt; int stk[N], top; bool in_stk[N]; int h[N], hs[N], e[M], ne[M], idx; int n, m, mod; int f[N], g[N]; unordered_set<ll> s; void add(int h[], int a, int b) // 添加一条边a->b { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void tarjan(int u) { dfn[u] = low[u] = ++tot; stk[++top] = u, in_stk[u] = 1; for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); } else if(in_stk[j]) low[u] = min(low[u], dfn[j]); } if(dfn[u] == low[u]) { ++cnt; int y; do{ y = stk[top--]; sz[cnt]++; id[y] = cnt; in_stk[y] = 0; }while(y != u); } } int main() { memset(h, -1, sizeof h); memset(hs, -1, sizeof hs); scanf("%d%d%d", &n, &m, &mod); for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); add(h, a, b); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int u = 1; u <= n; u++) //遍历所有边，挑选出不同连通分量之间的边 for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; int uid = id[u], jid = id[j]; ll hash = 1ll * uid * N + jid; //防止反复加入 if(uid != jid && !s.count(hash)) { s.insert(hash); add(hs, uid, jid); } } for(int u = cnt; u; u--) { if(!f[u]) { f[u] = sz[u]; //节点数 g[u] = 1; //图数 } for(int i = hs[u]; ~i; i = ne[i]) { int j = e[i]; if(f[j] < f[u] + sz[j]) { f[j] = (f[u] + sz[j]) % mod; g[j] = g[u]; } else if(f[j] == f[u] + sz[j]) g[j] = (g[j] + g[u]) % mod; } } int ans1 = 0, ans2 = 0; for(int i = 1; i <= cnt; i++) { if(f[i] > ans1) { ans1 = f[i]; ans2 = g[i]; } else if(f[i] == ans1) ans2 = (ans2 + g[i]) % mod; } printf("%d\n%d", ans1, ans2); }