直接枚举三元环超时因时间复杂度o(n³)，而按度数定向可将出度限制在o(√m)，使总复杂度降至o(m√m)；需统一建图、避免重复计数、用哈希集高效查边。
为什么直接枚举三元环会超时
暴力枚举三个点 u, v, w 判断是否两两连通，时间复杂度是 O(n³)，对稀疏图（比如边数 m ≈ 10⁵）完全不可行。更糟的是，实际图中三元环数量可能远超边数，但枚举方式根本没利用图的稀疏性。
定向的核心思想：把无向图变成有向无环图（DAG）
关键不是随便加方向，而是按「度数」定向：
对每条无向边 (u, v)，规定方向为 u → v 当且仅当 deg[u] ；若度数相等，则按节点编号小→大（避免平局）。这样构造出的有向图一定是无环的——因为沿有向边走，度数严格递增（或编号递增），不可能回到原点。
这个定向后，每个三元环在原图中只会在新图中以唯一一种方式出现：u → v、u → w、v → w（即一个“源点”指向两个“中间点”，两中间点之间也有边）。所以只需枚举每个点 u，遍历它的所有出边邻居 v 和 w，再检查 v 和 w 在新图中是否有边 v → w（或 w → v，但根据定向规则，只可能有一个方向存在）。
实操建议：
- 预处理每个点的度数
deg[i]，建图前就确定好定向规则 - 用邻接表存有向图，但为快速判断
v → w是否存在，建议对每个点的出边邻居用std::unordered_set或布尔数组（若点数不大）维护 - 枚举时只遍历
u的出边邻居，而非所有邻居，这是降复杂度的关键
时间复杂度为什么是 O(m√m)
定向后，任意点 u 的出度不会超过 O(√m)。证明思路：若 u 出度很大，说明它连向很多高度数点，而高度数点总数有限（度数和为 2m，所以度数 > √m 的点最多 2√m 个）；反过来，低度数点（≤ √m）最多只有 √m 个能被 u 指向（因为 u 自身度数也 ≤ √m）。综合两种情况，出度上界就是 O(√m)。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
因此总枚举量是所有点的「出度²」之和，最坏也不超过 n × (√m)² = n × m，但更紧的界是 O(m√m) —— 因为只有边数多的图才可能让多个点拥有接近 √m 的出度，而这类点数量受 m 约束。
容易漏掉的细节和坑
常见错误现象：
• 统计结果偏少：没按定向规则统一建有向图，比如对同一条边两次处理方向不一致
• 重复计数：误以为每个三元环会被多个源点触发，其实定向后每个环只被度数最小（或编号最小）的那个点作为源点捕获一次
• 查边慢：用邻接矩阵查 v → w 是 O(1) 但空间 O(n²)；用邻接表 + 线性扫描是 O(outdeg[v])，退化成 O(m)；必须用哈希集合或排序+二分
实操建议：
- 建有向图时，对每条输入边
(u, v)，先算deg[u]和deg[v]，再决定方向，不要依赖输入顺序 - 存储出边邻居时，推荐
vector<unordered_set>> out_edges(n)</unordered_set>，插入和查询都是均摊O(1) - 如果点编号稀疏或很大（如 1e9），先离散化；否则直接用数组下标
- 注意自环和重边：题目若允许，需在读入时去重并跳过自环，否则定向逻辑和查边都会出错
真正卡性能的地方往往不在算法主干，而在哈希表重建开销或离散化耗时——尤其是多次调用场景下，别在循环里反复构造 unordered_set。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
