AcWing.1175 最大半连通子图
题目描述
(qquad)一个有向图 (G = (V,E)) 称为半连通的,如果满足:(forall u,v in V),满足 (u o v) 或 (v o 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)到(A_2)是必定存在一条有某个分界点(uin A_1)和另一个点(vin A_2)之间有一条边,只要这样我们就可以保证(A_1和A_2)可以构成半连通子图(因为强连通分量内每个点都是“有关系的”)
(qquadqquad)所以我们这道题尽量跑长一点的链,这样我们最后构成的半连通子图才会尽量大
(qquad)因为已经是拓扑图,我们就可以通过拓扑序(DP),这样就可以很容易地得到它的最长链,顺便也可以统计出方案数,通过加法原理就可以得到下列方程
这边我们半连通子图的大小应该是
然后跑最长链,就行了。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
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<long long> 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
%d
", maxf, sum);
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击