环计数问题
普通环计数
例题 1：Codeforces Beta Round 11 D. A Simple Task
给定一个简单图，求图中简单环的数目．简单环是指没有重复顶点或边的环．
结点数目 1 ≤𝑛 ≤191≤n≤19
．
解题思路
考虑状态压缩动态规划．记 𝑓(𝑠,𝑖)f(s,i) 表示满足当前经过结点集合为 𝑠s，且现在在结点 𝑖i 上，且第一个结点为结点集合 𝑠s 中 编号最小的那个 的路径条数．
对于状态 𝑓(𝑠,𝑖)f(s,i)，枚举下一个结点 𝑢u．若 𝑢u 在集合 𝑠s 中且是编号最小的那个（即起点），就将答案 𝐴A 加上 𝑓(𝑠,𝑖)f(s,i)．若 𝑢u 不在 𝑠s 中，就将 𝑓(𝑠,𝑖)f(s,i) 加上 𝑓(𝑠 ∪{𝑢},𝑢)f(s∪{u},u)．
这样会把二元环（即重边）也算上，并且每个非二元环会被计算两次（因为固定起点可以向两个方向走），所以答案为 𝐴−𝑚2A−m2，其中 𝑚m 表示边数．时间复杂度 𝑂(2𝑛𝑚)O(2nm)．
示例代码
---|---
## 三元环计数
**三元环** 指的是一个简单图 𝐺G 中的一个无序三元组 (𝑢, 𝑣, 𝑤)(u, v, w) 满足存在三条边分别连接 (𝑢, 𝑣)(u, v)，(𝑣, 𝑤)(v, w) 和 (𝑤, 𝑢)(w, u)．而 **三元环计数问题** 要求计算出图中所有三元环的数量．
首先给所有边定向．我们规定从度数小的点指向度数大的点，度数相同就从编号小的点指向编号大的点．那么此时此图是一张有向无环图（DAG）．
该图没有环的证明
反证法，假设存在环，那么环中的点度数一个比一个大，要形成环，所有点的度数必须相等，但是编号必定不同，矛盾．
所以定向后图肯定不存在环．
事实上，可以根据上述定向规则构造一个 [偏序](../../math/order-theory/#二元关系)，所以按此规则构造的图（也即该偏序的 [Hasse 图](../../math/order-theory/#偏序集的可视化表示hasse-图)）一定是一个 DAG．
枚举 𝑢u 和 𝑢u 指向的点 𝑣v，再在 𝑣v 指向的点中枚举 𝑤w，检验 𝑢u 是否与 𝑤w 相连即可．
这个算法的时间复杂度为 𝑂(𝑚√𝑚)O(mm)．
时间复杂度证明
对于定向部分，遍历了所有的边，时间复杂度 𝑂(𝑛 +𝑚)O(n+m)．
对于每一对 (𝑣, 𝑤)(v, w)，𝑢u 的数量都不超过 𝑣v 的入度 𝑑−(𝑣)d−(v)．
若 𝑑−(𝑣) ≤√𝑚d−(v)≤m，由于 𝑤w 的个数至多为 𝑛n，所以这部分时间复杂度为 𝑂(𝑛√𝑚)O(nm)．
若 𝑑−(𝑣) >√𝑚d−(v)>m，由于 𝑣v 指向 𝑤w，所以 𝑑(𝑣) ≤𝑑(𝑤)d(v)≤d(w)，得出 𝑑(𝑤) >√𝑚d(w)>m，但是总边数只有 𝑚m，所以这样的 𝑤w 的个数至多为 √𝑚m，故时间复杂度为 𝑂(𝑚√𝑚)O(mm)．
总时间复杂度为 𝑂(𝑛 +𝑚 +𝑛√𝑚 +𝑚√𝑚) =𝑂(𝑚√𝑚)O(n+m+nm+mm)=O(mm)．
事实上，如果定向时从度数大的点指向度数小的点，复杂度也正确，只需要交换 𝑢, 𝑤u, w 两个点，上述证明也成立．
示例代码（[洛谷 P1989 无向图三元环计数](https://www.luogu.com.cn/problem/P1989)）
---|---
例题 2
给定一张有 𝑛n 个点和 𝑚m 条边的无向图，求下面图形的出现次数．
2 ≤𝑛 ≤1052≤n≤105，1 ≤𝑚 ≤min{2×105, 𝑛(𝑛−1)2}1≤m≤min{2×105, n(n−1)2}．
解题思路
这个图形是两个三元环共用了一条边形成的．所以我们先跑一遍三元环计数，统计出一条边上三元环的数量，然后枚举共用的那条边，设有 𝑥x 个三元环中有此边，那么对答案的贡献就是 (𝑥2)(x2)．
时间复杂度 𝑂(𝑚√𝑚)O(mm)．
示例代码
---|---
## 四元环计数
类似地，**四元环** 就是指四个点 𝑎, 𝑏, 𝑐, 𝑑a, b, c, d 满足 (𝑎, 𝑏)(a, b)，(𝑏, 𝑐)(b, c)，(𝑐, 𝑑)(c, d) 和 (𝑑, 𝑎)(d, a) 均有边连接．
考虑先对点进行排序．度数小的排在前面，度数大的排在后面．
考虑枚举排在最后面的点 𝑎a，此时只需要对于每个比 𝑎a 排名更前的点 𝑐c，都求出有多少个排名比 𝑎a 前的点 𝑏b 满足 (𝑎, 𝑏)(a, b)，(𝑏, 𝑐)(b, c) 有边．然后只需要从这些 𝑏b 中任取两个都能成为一个四元环．求 𝑏b 的数量只需要遍历一遍 𝑏b 和 𝑐c 即可．
注意到我们枚举的复杂度本质上与枚举三元环等价，所以时间复杂度也是 𝑂(𝑚√𝑚)O(mm)（假设 𝑛, 𝑚n, m 同阶）．
值得注意的是，(𝑎, 𝑏, 𝑐, 𝑑)(a, b, c, d) 和 (𝑎, 𝑐, 𝑏, 𝑑)(a, c, b, d) 可以是两个不同的四元环．
另外，度数相同的结点的排名将不相同，并且需要注意判断 𝑎 ≠𝑐a≠c．
示例代码（[LibreOJ P191 无向图四元环计数](https://loj.ac/p/191)）
---|---
例题 3
Gym 102028L Connected Subgraphs
给定一张有 𝑛n 个点和 𝑚m 条边的无向图，求四条边的导出子图连通的情况数．
4 ≤𝑛 ≤1054≤n≤105，4 ≤𝑚 ≤2 ×1054≤m≤2×105．
解题思路
容易把情况分为五种：菊花图、四元环、三元环上一个点连出一条边、四个点构成的链中间一个点连出一条边以及五个点构成的链．
菊花图直接枚举点的度数，用组合数解决即可．四元环可以直接按照上述算法求得．三元环部分只需枚举三元环 (𝑢, 𝑣, 𝑤)(u, v, w)，那么对答案的贡献就是 [𝑑(𝑢) −2] +[𝑑(𝑣) −2] +[𝑑(𝑤) −2][d(u)−2]+[d(v)−2]+[d(w)−2]．
下面考虑第四种情况．考虑枚举度数为 22 的点 𝑥x，再枚举与它相邻的一个结点 𝑦y 作为度数为 33 的那个点．此时对答案的贡献为 [𝑑(𝑥) −1] ⋅(𝑑(𝑦)−12)[d(x)−1]⋅(d(y)−12)．但是注意到 𝑦y 的相邻节点可能会和 𝑥x 的相邻结点重合，此时的图形等价于第三种情况．但是每种多算的第三种情况都会被多算两次（因为有两个度数为 33 的点），所以应该减去第三种情况数目的两倍．
对于最后一种情况，先枚举中间的点 𝑥x，那么容易发现对答案的贡献是
∑𝑦∈𝑠𝑜𝑛𝑥∑𝑧∈𝑠𝑜𝑛𝑥[𝑑(𝑦)−1]⋅[𝑑(𝑧)−1].∑y∈sonx∑z∈sonx[d(y)−1]⋅[d(z)−1].
同样地，这其中有多算的部分．设 𝑦y 的相邻结点为 𝑠s，𝑧z 的相邻结点为 𝑡t，那么思考后发现多算的有如下几种情况：
- 𝑦y 与 𝑡t 重合，但是 𝑠s 与 𝑧z 不重合时，等价于第三种情况；
- 𝑠s 与 𝑧z 重合，但是 𝑦y 与 𝑡t 不重合时，同样等价于第三种情况；
- 𝑦y 与 𝑡t，𝑠s 与 𝑧z 都重合时，等价于一个三元环；
- 𝑠s 与 𝑡t 重合时，等价于一个四元环（第二种情况）．
考虑到第三种情况中两个度数 22 的点作为 𝑥x 时正好分别对应上述多算情况的 1 和 2，所以要额外减去第三种情况数目的两倍．对于一个三元环，三个结点都可以作为 𝑥x，多算了 33 次．同样的，四元环的情况被多算了 44 次．
于是我们就得出了所有情况的算法，时间复杂度为 𝑂(𝑛 +𝑚√𝑚)O(n+mm)．
示例代码
---|---
## 习题
[洛谷 P3547 [POI2013] CEN-Price List](https://www.luogu.com.cn/problem/P3547)
[CodeForces 985G Team Players](https://codeforces.com/contest/985/problem/G)（容斥原理）
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/rings-count.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/rings-count.md "edit.link.title")
> __本页面贡献者：[Tiphereth-A](https://github.com/Tiphereth-A), [megakite](https://github.com/megakite), [Molmin](https://github.com/Molmin), [c-forrest](https://github.com/c-forrest), [Enter-tainer](https://github.com/Enter-tainer), [untitledunrevised](https://github.com/untitledunrevised)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用