无向图子图计数-摘抄_LCA
JueFan 一只绝帆

P1989 无向图三元环计数

小度连大度(或者大度连小度),复杂度 mmm\sqrt m,分讨易证。

四元环计数

考虑对点按度数排序,枚举最后面的点 aa,枚举它的对面点 cc,那么满足 a→b,(b,c)a\to b,(b,c) 有边的 bb 里随便选两个即可。

实际操作不需要排序,直接枚举 a→b,b↔ca\to b,b\leftrightarrow c,把 bb 的数量记在 cc 上,每次 aa 变动的时候清空这个记录。

注意 b,cb,c 之间是双向边(原图中的边),记得判断 a,ca,c 之间的大小关系,必须满足 a>ca>c,别漏了相等。

注意要大度连小度。

复杂度分析类似三元环。

Gym 102028L Connected Subgraphs

给定一张有 nn 个点和 mm 条边的无向图,无自环重边,求四条边的导出子图连通的情况数。

n≤105,m≤2×105n\le 10^5,m\le 2\times 10^5。

五种图:四元环、三元环加一边、三叉菊花(一叉长为 22)、四叉菊花、四边链。

设以上五种的数量是 a,b,c,d,ea,b,c,d,e,设图中三元环的数量为 ff。

这个题其实可以有重边,把边当作带权的即可。

考虑用若干种方式计算,看都算出了什么:

  • 每个点选四条边:dd。
  • 枚举边,一边选 11 条边,一边选 22 条边:c+2bc+2b。
  • 统计三元环,外加一条边:bb。
  • 统计四元环:aa。
  • 枚举四边链的中心点,求出选两条边的终点的 (deg−1)(deg-1) 的乘积的和:3f+4a+2b+e3f+4a+2b+e。

参考资料

无向图子图计数 - JerryTcl - 博客园

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量