【天天报资讯】AcWing.1175 最大半连通子图

题目描述

$\qquad$一个有向图 $G = (V,E)$ 称为半连通的，如果满足：$\forall u,v \in V$，满足 $u \to v$ 或 $v \to u$，即对于图中任意两点 $u,v$，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

$\qquad$若 $G’ = (V’,E’)$ 满足，$E’$ 是 $E$ 中所有和 $V’$ 有关的边，则称 $G’$ 是 $G$ 的一个导出子图。

【资料图】

$\qquad$若 $G’$ 是 $G$ 的导出子图，且 $G’$ 半连通，则称 $G’$ 为 $G$ 的半连通子图。

$\qquad$若 $G’$ 是 $G$ 所有半连通子图中包含节点数最多的，则称 $G’$ 是 $G$ 的最大半连通子图。

$\qquad$给定一个有向图 $G$，请求出 $G$ 的最大半连通子图拥有的节点数 $K$，以及不同的最大半连通子图的数目 $C$。

$\qquad$由于 $C$ 可能比较大，仅要求输出 $C$ 对 $X$ 的余数。

解题思路

$\qquad$还是先从拓扑图$DAG$的角度来思考，毕竟不是$DAG$我们也可以用Tarjan把它缩点成$DAG$。$\qquad$在一张图上，一个强连通分量必定是半连通子图，一条链上的若干个强连通分量，也必定可以构成半连通子图，为什么？假设是这样一个串

\[A_1\Rightarrow A_2\Rightarrow A_3\Rightarrow A_4\Rightarrow A_5\Rightarrow A_6\]

从$A_1$到$A_2$是必定存在一条有某个分界点$u\in A_1$和另一个点$v\in A_2$之间有一条边，只要这样我们就可以保证$A_1和A_2$可以构成半连通子图（因为强连通分量内每个点都是“有关系的”）

\[因而可以推出$A_2和A_3$也可以构成半连通子图，因此整条链都可以构成半连通子图。\]

$\qquad\qquad$所以我们这道题尽量跑长一点的链，这样我们最后构成的半连通子图才会尽量大

$\qquad$因为已经是拓扑图，我们就可以通过拓扑序$DP$，这样就可以很容易地得到它的最长链，顺便也可以统计出方案数，通过加法原理就可以得到下列方程

\[\begin{array}c1.当f[k]=0，也就是没有被更新过的时候\\f[k] = sz[k]\\g[k]=1\\2.当f[k] < f[i] + sz[k] （发现更长的链可以更新）\\f[k] = f[i] + sz[k]\\g[k] = g[i] （所有从走到i的，再从i走到k是唯一的）\\3.当f[k]=f[i]+sz[k] （发现一样长的链一起选）\\g[k] += g[i] （顺便取模）\end{array}\]

这边我们半连通子图的大小应该是

\[整条链上所有的强连通分量内点的个数和\]

然后跑最长链，就行了。

代码

#include #include #include #include using namespace std;const int N = 1e5 + 10, M = 2e6 + 10;int h[N], hs[N], e[M], ne[M], idx;int stk[N], top, in_stk[N];int dfn[N], low[N], stmp, scc_cnt;int f[N], g[N], maxf, sum, id[N];int n, m, mod, sz[N];void add(int *h, int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void tarjan(int u) {    dfn[u] = low[u] = ++ stmp;    stk[ ++ top] = u, in_stk[u] = true ;        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])     {        int y; ++ scc_cnt;        do         {            y = stk[top -- ];            in_stk[y] = false ;            id[y] = scc_cnt;            sz[scc_cnt] ++ ;        } while (y != u);    }}int main() {    scanf("%d%d%d", &n, &m, &mod);        memset(h, -1, sizeof h);    memset(hs, -1, sizeof hs);        while (m -- )     {        int u, v;        scanf("%d%d", &u, &v);        add(h, u, v);    }        for (int i = 1; i <= n; i ++ )         if (!dfn[i]) tarjan(i);            unordered_set mp;        for (int i = 1; i <= n; i ++ )     {        for (int j = h[i]; ~j; j = ne[j])         {            int k = e[j], a = id[i], b = id[k];            if (a != b && !mp.count(a * 1e6 + b))             {                add(hs, a, b);                mp.insert(a * 1e6 + b);            }        }    }        for (int i = scc_cnt; i; i -- )     {        if (!f[i])         {            f[i] = sz[i];            g[i] = 1;        }        for (int j = hs[i]; ~j; j = ne[j])         {            int k = e[j];            if (f[k] < f[i] + sz[k])             {                f[k] = f[i] + sz[k];                g[k] = g[i];            }            else if (f[k] == f[i] + sz[k])             {                g[k] += g[i];                if (g[k] >= mod) g[k] -= mod;            }        }    }        for (int i = scc_cnt; i; i -- )     {        if (f[i] > maxf)             maxf = f[i], sum = g[i];        else if (f[i] == maxf)        {            sum += g[i];            if (sum >= mod) sum -= mod;        }    }        printf("%d\n%d\n", maxf, sum);        return 0;}