无向图子图计数-摘抄_LCA

P1989 无向图三元环计数

小度连大度（或者大度连小度），复杂度 $m\sqrt m$，分讨易证。

四元环计数

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

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

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

注意要大度连小度。

复杂度分析类似三元环。

Gym 102028L Connected Subgraphs

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

$n\le 10^5,m\le 2\times 10^5$。

五种图：四元环、三元环加一边、三叉菊花（一叉长为 $2$）、四叉菊花、四边链。

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

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

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

• 每个点选四条边：$d$。
• 枚举边，一边选 $1$ 条边，一边选 $2$ 条边：$c+2b$。
• 统计三元环，外加一条边：$b$。
• 统计四元环：$a$。
• 枚举四边链的中心点，求出选两条边的终点的 $(deg-1)$ 的乘积的和：$3f+4a+2b+e$。

参考资料

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