企业官网建设流程全解析

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) ≥ k（u 的出边指向的邻居度数都不小于 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^6，m√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; vector<int> adj[MAXN]; // 原无向图邻接表 int deg[MAXN]; // 每个点的度数 pair<int,int> edges[MAXM]; // 存储所有无向边 vector<int> 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，然后再建图。

vector<pair<int,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 常见问题速查表

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 KB，n 个 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，尤其是定向规则不一致、重边未处理、标记数组未初始化这些问题。对拍的时候记得多跑几组随机数据，覆盖各种度数分布的情况，比如所有点度数相等、度数差异很大、有孤立点等。这样能确保你的程序在各种边界情况下都正确。