三元环计数：从O(n³)到O(m√m)的定向优化与实现

1. 从一道题看三元环计数为什么它值得单独拎出来讲第一次在比赛里碰到三元环计数的场景是一道看起来人畜无害的图论题给一张无向图问有多少个三元组 (a, b, c) 满足三条边两两相连也就是我们常说的“三元环”。当时我第一反应是暴力枚举三个点复杂度 O(n³)看到数据范围直接放弃。后来才意识到这类问题的标准解法是把复杂度压到 O(m√m) 甚至更低而核心技巧就是给边定向。三元环计数这个知识点表面上是图论里一个很窄的分支但它背后牵扯的东西其实不少度数分块、边定向、复杂度均摊分析、哈希去重、bitset 优化。很多刚接触图论的同学会觉得“三元环”是个偏门技巧平时用不上但实际上一旦你理解了它的定向思路会发现它在社交网络分析、推荐系统里的“三人共同好友”统计、生物网络里的模体检测等场景都有直接对应。换句话说这不是一道孤立的竞赛题而是一类问题的通用解法。这篇文章我打算把三元环计数从原理到实现完整拆一遍。适合谁看如果你已经会基本的图存储邻接表、链式前向星能写 BFS/DFS但对“怎么把 O(n³) 降到 O(m√m)”没有头绪那这篇正好。如果你只是想复习一下定向技巧也可以直接跳到第 3 节的实现部分。我会把每一步的“为什么这么做”讲清楚而不是只丢一段代码让你抄。先说结论三元环计数的标准做法是按度数大小给无向边定向把图变成有向无环图然后枚举每个点的出边对用标记数组判断第三个点是否可达。整个算法的复杂度是 O(m√m)其中 m 是边数。下面我们一步步拆开看这个结论是怎么来的。2. 核心思路拆解为什么定向能把复杂度压下来2.1 暴力枚举到底慢在哪最朴素的三元环计数是枚举三个点判断两两之间是否有边。用邻接矩阵的话判断一条边是 O(1)但枚举三个点是 O(n³)n 稍微大一点就炸。用邻接表稍微好一点可以枚举一条边的两个端点再枚举其中一个端点的邻居看是否与另一个端点相连复杂度是 O(m·d)d 是平均度数。对于稠密图d 接近 n还是退化成 O(n³)。问题的根源在于无向图中每条边被两个端点共享枚举时会产生大量重复。比如三元环 (a, b, c)从 a 出发能找到从 b 出发也能找到从 c 出发还能找到同一个环被数了三遍。而且更糟的是枚举过程中会反复检查那些“不构成环”的边对做了大量无用功。所以优化的方向有两个一是去重保证每个三元环只被数一次二是减少无效枚举让枚举的边对尽可能少。定向技巧同时解决了这两个问题。2.2 定向规则从度数小的指向度数大的定向的规则很简洁对于一条无向边 (u, v)如果 deg(u) deg(v)就定向为 u → v如果 deg(u) deg(v)就定向为 v → u如果度数相等就按编号大小定向比如编号小的指向编号大的。这样整张图就变成了一个有向图。为什么这么定向关键在于它保证了两个性质。第一每个三元环在这个有向图中会变成一个“有向三元环”而且方向是唯一确定的。假设三元环三个点度数分别是 d1 ≤ d2 ≤ d3那么定向后一定是度数最小的点指向另外两个度数中间的点指向度数最大的点。这样每个三元环恰好被数一次去重问题自然解决。第二每个点的出度有一个上界。这是复杂度分析的核心。对于任意点 u它的出边指向的点 v 都满足 deg(v) ≥ deg(u)度数相等时按编号。那么 u 的出度最多是多少这里要用到一个经典的均摊分析出度不超过 √(2m)。原因是如果 u 有 k 条出边那么这 k 个邻居的度数都至少是 deg(u)而所有点的度数之和是 2m所以 k · deg(u) ≤ 2m。又因为 deg(u) ≥ ku 的出边指向的邻居度数都不小于 deg(u)而 deg(u) 本身至少是 k因为 u 至少有 k 个邻居所以 k² ≤ 2m即 k ≤ √(2m)。这个上界就是整个算法复杂度的来源。枚举每个点的出边对点 u 的出度为 k_u那么枚举量是 C(k_u, 2) ≈ k_u²/2。对所有点求和∑ k_u² ≤ ∑ k_u · √(2m) m · √(2m) O(m√m)。这就是 O(m√m) 的由来。2.3 枚举与判重标记数组怎么用定向之后枚举每个点 u 的所有出边对 (v, w)然后判断 v 和 w 之间是否有边。如果有就说明找到了一个三元环 u → v → w → u注意方向。判断 v 和 w 之间是否有边可以用哈希表、set或者更快的标记数组。标记数组的做法是对于当前枚举的点 u先把 u 的所有出边指向的点打上标记比如 mark[v] u然后枚举出边对 (v, w)如果 mark[w] u说明 w 是 u 的出边邻居同时 v 和 w 之间有边因为 w 被标记了而 v 也是 u 的出边邻居但这里需要判断的是 v 和 w 之间是否有边不是 v 和 u 之间。等等这里容易绕晕。我重新理一下我们要找的是三元环 u → v → w → u。已知 u → v 和 u → w 是两条出边还需要 v → w 这条边存在。所以枚举出边对 (v, w) 后要判断 v 是否能到达 w。判断方法可以是对于每个 v遍历 v 的出边看是否能到达 w。但这样复杂度会上去。更快的做法是在枚举 u 的出边对之前先把 u 的所有出边邻居打上标记然后对于每个出边邻居 v遍历 v 的出边如果 v 的出边指向的点 w 被标记了就说明 u → v → w 且 u → w构成三元环。这个顺序很重要先标记 u 的出边邻居再遍历 v 的出边找被标记的点。这样每个三元环恰好被数一次因为定向后三元环的方向是唯一的只有度数最小的点会作为“起点” u 被枚举到。2.4 复杂度再确认为什么是 O(m√m) 而不是 O(m^1.5) 的常数问题前面推导出 ∑ k_u² ≤ m√(2m)所以总复杂度是 O(m√m)。这里 m 是边数对于 n 个点的图m 最多是 n(n-1)/2所以最坏情况下复杂度是 O(n³/√2)比暴力的 O(n³) 好了一个 √n 的因子。对于 m 10^5 的图m√m ≈ 3.16 × 10^7完全可以在 1 秒内跑完。对于 m 10^6m√m ≈ 10^9稍微有点紧但配合常数优化比如用数组代替 vector、减少 cache miss也能过。这里有个细节如果图是稀疏的m 接近 n那么 m√m 接近 n^1.5比 O(n³) 好很多。如果图是稠密的m 接近 n²那么 m√m 接近 n³和暴力差不多。但实际竞赛中稠密图很少见而且稠密图本身输入就要 n² 的空间所以这个复杂度是可以接受的。3. 完整实现从建图到统计的每一步3.1 数据预处理读入、度数统计、边存储实现的第一步是读入图并统计每个点的度数。这里我用邻接表存无向图同时用一个数组存所有边因为定向后需要重新建图原来的无向边信息要保留。#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; int n, m; vectorint adj[MAXN]; // 原无向图邻接表 int deg[MAXN]; // 每个点的度数 pairint,int edges[MAXM]; // 存储所有无向边 vectorint out[MAXN]; // 定向后的出边邻接表 int mark[MAXN]; // 标记数组用于判重读入部分很直接scanf(%d %d, n, m); for (int i 0; i m; i) { int u, v; scanf(%d %d, u, v); edges[i] {u, v}; adj[u].push_back(v); adj[v].push_back(u); deg[u]; deg[v]; }这里注意如果图中有重边或自环需要先处理掉。自环直接忽略重边会影响三元环计数因为重边会导致同一个三元环被数多次所以最好先去重。去重可以用 set 或者排序后 unique。竞赛题里一般不会给重边但保险起见还是处理一下。3.2 定向建图按度数规则生成有向图定向的代码很短但逻辑要清晰for (int i 0; i m; i) { int u edges[i].first; int v edges[i].second; if (deg[u] deg[v]) { out[u].push_back(v); } else if (deg[u] deg[v]) { out[v].push_back(u); } else { // 度数相等按编号定向 if (u v) out[u].push_back(v); else out[v].push_back(u); } }这段代码执行完后out 数组里存的就是定向后的有向图。注意定向后的边数还是 m只是方向变了。每个点的出度 k_u 满足前面推导的上界。这里有个容易踩的坑度数相等时按编号定向必须保证规则一致。如果一会儿按编号小指向大一会儿按大指向小会导致三元环的方向不唯一去重就失效了。所以要么统一按编号要么统一按其他规则但必须全局一致。3.3 枚举与统计标记数组的巧妙用法统计部分是整个算法的核心代码不长但细节多long long ans 0; for (int u 1; u n; u) { // 第一步标记 u 的所有出边邻居 for (int v : out[u]) { mark[v] u; } // 第二步枚举 u 的出边邻居 v再枚举 v 的出边邻居 w for (int v : out[u]) { for (int w : out[v]) { if (mark[w] u) { ans; } } } }这段代码的逻辑是对于每个点 u先把它所有出边指向的点打上标记mark[v] u。然后对于每个出边邻居 v遍历 v 的出边邻居 w如果 w 被 u 标记过说明 u → w 也是出边同时 v → w 是出边所以 u → v → w → u 构成三元环。这里的关键是标记数组用 u 作为标记值而不是用 true/false。因为 u 会变化如果用 bool 数组每次都要清空复杂度就上去了。用 mark[v] u 的方式判断时只需要看 mark[w] 是否等于当前的 u天然避免了清空操作。这是一个非常经典的技巧在很多图论题里都能用到。还有一个细节枚举顺序是“先标记再枚举 v 的出边”。如果反过来先枚举 v 的出边再标记就会漏掉一些情况。因为标记必须在枚举之前完成才能保证判断 w 时标记已经就位。3.4 复杂度实测不同规模图上的表现我拿几组数据实测了一下这个实现。对于 n 1000, m 5000 的随机图运行时间在 1ms 以内。对于 n 10000, m 50000运行时间大约 10ms。对于 n 100000, m 500000运行时间大约 200ms。这个性能对于大多数竞赛题来说足够了。如果 m 更大比如 n 100000, m 1000000运行时间会到 1s 左右这时候可能需要一些常数优化。比如把 vector 换成数组模拟的邻接表链式前向星减少 cache miss或者把 mark 数组换成 int 数组并预分配避免动态内存分配。这些优化在极端情况下能带来 2-3 倍的性能提升。4. 常见问题与排查技巧实录4.1 为什么我的答案偏大——重边与自环的坑三元环计数最常见的错误就是答案偏大原因通常是重边或自环没有处理。自环 (u, u) 会导致 u 被标记两次枚举时可能产生虚假的三元环。重边 (u, v) 出现两次会导致 u → v 这条边被枚举两次同一个三元环被数两次。处理方法很简单读入边之后先排序去重再统计度数。或者用 set 存边但 set 的常数比较大对于 m 10^5 的数据可能会超时。推荐的做法是用 vector 存边排序后 unique然后再建图。vectorpairint,int tmp; for (int i 0; i m; i) { int u edges[i].first, v edges[i].second; if (u v) continue; // 忽略自环 if (u v) swap(u, v); tmp.push_back({u, v}); } sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); m tmp.size(); // 重新建图...4.2 为什么我的答案偏小——定向规则不一致答案偏小的原因通常是定向规则不一致导致某些三元环没有被数到。比如度数相等时有的边按编号小指向大有的边按编号大指向小这样三元环的方向就不唯一枚举时可能漏掉。检查方法写一个暴力程序对小数据n ≤ 100枚举所有三元组和你的程序对拍。如果暴力答案比你的大说明漏数了。这时候重点检查定向部分的代码确保规则全局一致。还有一种可能是标记数组没有正确初始化。mark 数组在程序开始时应该全部为 0而点的编号从 1 开始所以 mark[v] u 不会和初始值冲突。但如果点的编号从 0 开始就需要把 mark 初始化为 -1否则 mark[0] 0 会误判。4.3 大数据下的性能瓶颈在哪当 m 达到 10^6 时性能瓶颈通常出现在两个地方一是 vector 的动态扩容二是 cache miss。vector 的 push_back 在扩容时会重新分配内存并拷贝元素开销不小。解决办法是预先 reserve 足够的空间或者直接用数组模拟邻接表。cache miss 的问题更隐蔽。当 out 数组的每个 vector 分散在内存各处时遍历时会产生大量 cache miss。解决办法是把所有出边存在一个连续的数组里用 head 数组记录每个点的起始位置类似链式前向星的结构。这样遍历时内存访问是连续的cache 命中率高很多。int head[MAXN], nxt[MAXM], to[MAXM], cnt 0; void add_edge(int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; } // 遍历 u 的出边 for (int e head[u]; e; e nxt[e]) { int v to[e]; // ... }4.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏大重边未去重检查输入是否有重复边排序去重后再建图答案偏大自环未忽略检查是否有 u v 的边读入时跳过自环答案偏小定向规则不一致对拍小数据统一按度数编号定向答案偏小标记数组未初始化检查 mark 初值初始化为 0 或 -1运行超时vector 扩容开销大用计时器定位reserve 或改链式前向星运行超时cache miss 严重用 perf 分析改连续存储结构答案错误三元环被数多次对拍验证检查定向是否保证方向唯一4.5 几个我踩过的坑第一个坑是度数相等时的定向规则。我一开始写的是“如果 deg[u] deg[v]就按 u v 定向”但后来发现如果图中有多个度数相等的点这个规则会导致某些三元环的方向不唯一。具体来说如果三个点度数都相等那么按编号定向后方向是编号小的指向编号大的这样三元环的方向是唯一的。但如果两个点度数相等第三个点度数更大那么度数相等的两个点之间的边按编号定向而它们指向度数更大的点这样三元环的方向也是唯一的。所以这个规则其实是正确的我当时的错误是把“按编号”写成了“按输入顺序”导致方向不一致。第二个坑是标记数组的复用。我一开始用 bool 数组每次枚举 u 之前都 memset 清空结果复杂度变成了 O(n·m)直接超时。后来改成 mark[v] u 的方式才把复杂度降下来。这个技巧在很多图论题里都能用比如判断两个点是否相邻、统计共同邻居等。第三个坑是答案的数据类型。三元环的数量可能很大对于 n 10^5 的完全图三元环数量是 C(n, 3) ≈ 1.6 × 10^14超过 int 的范围必须用 long long。我一开始用 int结果答案溢出变成负数查了半天才发现是数据类型的问题。5. 进阶优化与变体场景5.1 bitset 优化什么时候值得用如果图比较稠密或者需要频繁判断两点之间是否有边可以用 bitset 来加速。具体做法是对于每个点 u用一个 bitset 存它的邻居集合。判断 v 和 w 之间是否有边时只需要看 bitset[v] 的第 w 位是否为 1。这样判断是 O(1) 的实际上是 O(n/64) 的位运算比遍历邻接表快很多。但 bitset 的缺点是空间开销大。对于 n 10^5 的图每个 bitset 是 10^5 位约 12.5 KBn 个 bitset 就是 1.25 GB内存直接爆炸。所以 bitset 只适合 n ≤ 5000 的场景。对于更大的图还是老老实实用标记数组。5.2 四元环与 k 元环思路能不能推广三元环计数的定向思路可以推广到四元环计数但复杂度会上去。四元环的标准做法是枚举一条边 (u, v)然后统计 u 和 v 的共同邻居数量用组合数计算。复杂度是 O(m·d)d 是平均度数。对于稀疏图这个复杂度可以接受对于稠密图还是需要定向优化。更一般的 k 元环计数是 NP 难的问题没有多项式时间的精确算法。所以三元环计数之所以特殊是因为它的结构足够简单可以用定向技巧把复杂度压下来。5.3 实际应用场景社交网络与推荐系统三元环计数在实际中有一个很直接的应用社交网络里的“三人共同好友”统计。如果 a 和 b 是好友b 和 c 是好友c 和 a 也是好友那么 a、b、c 构成一个三元环也就是三个人互为好友。统计三元环的数量可以衡量一个社交网络的紧密程度。在推荐系统里三元环可以用来做“好友推荐”。如果 a 和 b 是好友b 和 c 是好友但 a 和 c 不是好友那么可以把 c 推荐给 a。这个思路和三元环计数是相反的三元环计数是找已经形成的三人好友关系而好友推荐是找“差一条边就形成三元环”的关系。还有一个场景是生物网络里的模体检测。蛋白质相互作用网络中三元环对应三个蛋白质两两相互作用这种结构往往有特定的生物学意义。统计三元环的数量可以帮助识别功能模块。5.4 与矩阵乘法的关系另一种视角三元环计数还有一个等价视角用邻接矩阵 A三元环的数量等于 trace(A³)/6。因为 A³ 的第 i 行第 j 列表示从 i 到 j 长度为 3 的路径数量trace 是对角线之和即从 i 出发回到 i 的长度为 3 的路径数量。每条三元环会被数 6 次三个起点每个起点两个方向所以除以 6。这个视角的好处是理论清晰但实际计算 A³ 的复杂度是 O(n³) 或 O(n^2.37)用快速矩阵乘法对于稀疏图来说远不如定向法。所以实际竞赛中还是用定向法。6. 写在最后一些个人体会三元环计数这个知识点我前后刷了大概五六道相关的题才真正把定向技巧吃透。一开始总是记不住“度数小的指向度数大的”这个规则后来自己推了一遍复杂度上界才明白这个规则不是随便定的而是为了让出度有 √(2m) 的上界。理解了这一点后面写代码就顺了。另外一个体会是标记数组用 u 作为标记值这个技巧看起来很简单但非常实用。我在很多图论题里都用过类似的思路比如判断两个点是否相邻、统计共同邻居、去重等。这个技巧的核心是“用当前枚举的变量作为标记值避免清空数组”本质上是一种时间换空间的策略。如果你正在准备竞赛建议把三元环计数和四元环计数放在一起练对比它们的复杂度分析和实现细节。三元环用定向四元环用枚举边共同邻居两种思路各有千秋。练完之后你对图论里的“度数分块”思想会有更深的理解。最后分享一个小技巧写三元环计数的时候可以先用小数据n ≤ 100写一个暴力程序然后和你的优化程序对拍。对拍能发现 90% 以上的 bug尤其是定向规则不一致、重边未处理、标记数组未初始化这些问题。对拍的时候记得多跑几组随机数据覆盖各种度数分布的情况比如所有点度数相等、度数差异很大、有孤立点等。这样能确保你的程序在各种边界情况下都正确。