最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

【天天报资讯】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;}

关键词: 连通分量 导出子图 加法原理