1. 从一道题看三元环计数的本质第一次看到这个题目的时候我盯着Counting Stars这个标题愣了几秒——星星和三元环有什么关系后来把题面读完才反应过来这里的star指的是图论中一种特殊的子图结构一个中心点连接三个外围点外围点之间再互相连边整体看起来像一个三角形外加一根尾巴形状确实有点像简笔画里的星星。而题目要求的是统计一个无向图中所有这样的星星结构数量。这道题的核心难点其实不在星星本身而在于三元环计数——也就是在一个无向图里找出所有三个点两两相连的三角形结构。为什么因为每一个三元环恰好可以贡献三个不同的星星三角形的任意一个顶点作为中心另外两个顶点加上中心自己构成的三元组再配上中心到第三个点的边就形成了一个star。所以整道题的解法可以拆成两步先枚举出图中所有的三元环然后对每个三元环看它的三个顶点各自还能连出去多少条边不包括三角形内部的边把这三个数加起来就是答案。听起来逻辑很清晰但真正动手写的时候问题就来了怎么高效地枚举三元环如果图比较稀疏直接暴力枚举三个点判断是否两两相连复杂度是O(n³)n稍微大一点就超时。如果图比较稠密用邻接矩阵倒是能O(1)判断边是否存在但n³的枚举量依然摆在那里。所以这道题真正考察的是一种经典的三元环计数技巧它能把复杂度压到O(m√m)级别其中m是边数。这个技巧在竞赛圈里有个约定俗成的名字叫按度数定向或者根号分治定向。我第一次接触这个技巧的时候觉得它特别巧妙——它没有用什么高深的算法只是对边做了一个简单的方向约定就把无序的三角形枚举变成了有序的、不重不漏的扫描。下面我就把这个技巧的来龙去脉、实现细节、以及我在实际写题过程中踩过的坑完整地梳理一遍。2. 三元环计数的核心思路给边定一个方向2.1 为什么直接枚举会出问题假设图中有n个点、m条边。最朴素的枚举方式是三重循环遍历所有点对判断是否两两相连。这个复杂度是O(n³)在n1000的时候就是10亿次操作显然不可接受。稍微优化一点可以只枚举存在的边对于每条边(u,v)再枚举u的所有邻居w判断v和w之间是否有边。这样复杂度是O(m·d)其中d是点的平均度数。在最坏情况下比如一个完全图m≈n²/2d≈n复杂度就退化成了O(n³)。问题的根源在于同一个三元环会被重复枚举多次。一个三角形有三条边如果对每条边都做一次枚举邻居再判断的操作这个三角形就会被数到三次。而且更麻烦的是即使我们想办法去重枚举的总量本身也没有减少——每条边都要扫一遍它端点的邻居这个开销是实打实的。2.2 定向的核心思想让每个三元环只被数一次这个技巧的关键洞察是如果我们能给图中的每条边规定一个方向使得每个三元环恰好有一个出度为2的顶点那么我们就可以只从这个顶点出发去枚举三元环做到不重不漏。具体怎么做对于一条无向边(u,v)我们比较u和v的度数如果度数相同就比较编号。规定方向从度数大的点指向度数小的点如果度数相同就从编号大的指向编号小的。这样整个无向图就变成了一个有向无环图因为度数严格递减或者编号严格递减不可能形成环。在这个定向规则下一个三元环(u,v,w)中必然存在一个唯一的顶点它的出度为2——也就是说它同时指向另外两个顶点。这个顶点就是三元环中度数最大或编号最大的那个。于是我们只需要枚举每个点u再枚举u的所有出边指向的点v再枚举v的所有出边指向的点w判断u和w之间是否有边。如果有就找到了一个三元环且这个三元环是以u为出度为2的顶点被唯一发现的。2.3 复杂度分析为什么是O(m√m)这个定向规则下每个点的出度有一个上界。假设一个点u的出度为out(u)那么对于u的每一条出边(u,v)都有deg(u) ≥ deg(v)或者度数相同但编号更大。可以证明out(u) ≤ √(2m)。为什么呢因为u的所有出边指向的点v它们的度数都至少是deg(u)在度数相同的情况下编号更小但度数不会更小。而这些点各自的度数之和至少是out(u)·deg(u)同时这个和不会超过2m所有点的度数之和是2m。所以out(u)·deg(u) ≤ 2m而deg(u) ≥ out(u)因此out(u)² ≤ 2m即out(u) ≤ √(2m)。于是枚举的总复杂度是对每个点u枚举它的出边v总共m条出边再枚举v的出边w每条出边v的出度不超过√(2m)所以总复杂度是O(m√m)。对于m10⁵级别的图m√m大约是3×10⁷完全可以在1秒内跑完。3. 实现细节从建图到统计的完整流程3.1 数据读入与度数统计第一步是读入所有的边同时统计每个点的度数。这里有个细节需要注意题目中的图可能有重边或者自环吗一般来说三元环计数问题中自环不会影响结果因为自环不参与三角形但重边会导致同一个三角形被重复计数。所以稳妥的做法是先去重或者在建图时用set来存储边。不过大多数题目保证没有重边具体要看题面。int n, m; vectorpairint,int edges; vectorint deg(n1, 0); for (int i 0; i m; i) { int u, v; cin u v; edges.push_back({u, v}); deg[u]; deg[v]; }3.2 按定向规则建立有向图接下来根据度数比较规则把每条无向边变成有向边。如果deg[u] deg[v]或者deg[u] deg[v] u v那么方向从u指向v否则从v指向u。vectorvectorint out(n1); // 出边邻接表 for (auto [u, v] : edges) { if (deg[u] deg[v] || (deg[u] deg[v] u v)) { out[u].push_back(v); } else { out[v].push_back(u); } }这里用vectorvector 来存出边邻接表是因为总边数m不算太大vector的动态扩容开销可以接受。如果m特别大比如10⁶可以考虑用链式前向星来节省内存和加快访问速度。3.3 标记数组的使用技巧枚举三元环的时候我们需要快速判断两个点之间是否有边。有两种常见做法一是用哈希表或者set来存边查询O(log m)二是用一个标记数组在枚举u的出边时先把u的所有出边指向的点打上标记然后枚举v的出边w时直接看w是否被标记。第二种做法查询是O(1)的整体更快。vectorint mark(n1, 0); long long ans 0; for (int u 1; u n; u) { // 先标记u的所有出边指向的点 for (int v : out[u]) { mark[v] u; // 用u作为标记值避免每次清空数组 } // 枚举u的出边v再枚举v的出边w for (int v : out[u]) { for (int w : out[v]) { if (mark[w] u) { // 找到一个三元环 u - v - w且u - w // 这里可以统计答案 } } } }这里用mark数组配合u作为标记值是一个很实用的小技巧——避免了每次枚举前都要memset清空数组把清空的开销分摊到了每次赋值上。3.4 统计星星数量的具体计算对于每个找到的三元环(u,v,w)我们需要计算以u、v、w分别为中心时能形成多少个星星。以u为中心为例星星的数量等于u的度数减去2减去三角形内部的两条边u-v和u-w因为u还可以连向其他点每连一个点就多一个星星。所以对于三元环(u,v,w)贡献的星星总数是(deg[u] - 2) (deg[v] - 2) (deg[w] - 2)注意这里的deg是原无向图中的度数不是定向后的出度。因为星星的外围点可以是任意方向上的邻居。if (mark[w] u) { ans (long long)(deg[u] - 2) (deg[v] - 2) (deg[w] - 2); }这里要用long long来存答案因为最坏情况下答案可能达到O(n³)级别int会溢出。4. 那些年我踩过的坑与优化经验4.1 重边导致的重复计数我第一次写这道题的时候没有考虑重边的情况结果WA了好几发。后来发现如果输入中有重边比如u和v之间有两条边那么在定向后out[u]中会有两个vout[v]中会有两个u如果方向是u-v的话。这样在枚举时同一个三元环会被数到多次。解决办法是在读入边的时候用set去重或者在建图前先对边排序去重。sort(edges.begin(), edges.end()); edges.erase(unique(edges.begin(), edges.end()), edges.end());不过要注意去重后m会变小度数统计也要重新做。所以稳妥的流程是先读入所有边到vector排序去重然后再统计度数、建图。4.2 标记数组的初始化问题用mark数组配合u作为标记值确实很巧妙但有一个前提u的值必须是唯一的且不会与之前的标记冲突。如果点的编号是从1到n那么用u作为标记值是完全没问题的因为每次枚举新的u时mark数组中等于u的位置一定是上一次枚举u时留下的而这次枚举会覆盖掉。但如果点的编号有0或者负数就需要额外处理。另外如果n特别大比如10⁶mark数组的内存开销也要考虑不过一般int数组10⁶也就是4MB可以接受。4.3 出边邻接表的遍历顺序在枚举v的出边w时如果out[v]很大遍历开销会比较大。虽然理论上out[v] ≤ √(2m)但在实际数据中某些点的出度可能接近这个上界。一个优化技巧是在枚举u的出边v时如果out[v]的大小加上当前已找到的三元环数量已经超过了某个阈值可以考虑提前终止或者换一种枚举方式。不过对于大多数题目来说直接暴力枚举已经足够快不需要过度优化。4.4 答案溢出的问题这道题的答案可能非常大。假设图是一个完全图n1000那么三元环的数量是C(1000,3)≈1.66×10⁸每个三元环贡献的星星数量大约是3×(n-3)≈3000总答案大约是5×10¹¹远超int的范围。所以必须用long long。我在第一次提交时就是因为用了int结果WA了后来改成long long就过了。4.5 常数优化用数组代替vector如果m比较大比如10⁶vectorvector 的动态扩容和内存碎片可能会成为瓶颈。这时候可以用链式前向星来存图或者用一个一维数组加偏移量来模拟邻接表。具体做法是先统计每个点的出度然后计算前缀和得到每个点在数组中的起始位置最后把边填入数组。这样遍历时是连续内存访问缓存友好速度会快很多。vectorint head(n1, -1), nxt(m), to(m); int cnt 0; auto add_edge [](int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; };这种写法在竞赛中很常见虽然代码稍微复杂一点但在大数据量下性能提升明显。5. 从三元环到更一般的子图计数5.1 四元环计数的类似思路三元环计数的定向技巧可以推广到四元环计数。对于四元环我们可以枚举一条边(u,v)然后枚举u的邻居w和v的邻居x判断w和x之间是否有边。但这样复杂度会高一些。更高效的做法是先按度数定向然后枚举每个点u再枚举u的出边v再枚举v的出边w最后枚举w的出边x判断x是否等于u或者与u相邻。不过四元环的计数要复杂得多因为一个四元环可能被多种方式枚举到需要仔细去重。5.2 三元环计数在实际问题中的应用三元环计数不仅仅是一道竞赛题它在实际中也有很多应用。比如在社交网络分析中三元环也叫三角形是衡量网络聚集系数的重要指标。一个社交网络中三角形越多说明用户之间的关系越紧密社区结构越明显。在推荐系统中如果两个用户有共同的好友即他们和共同好友构成三角形那么他们很可能也认识可以用来做好友推荐。在生物信息学中蛋白质相互作用网络中的三角形结构往往对应着功能模块。5.3 根号分治思想的通用性这道题背后的根号分治思想非常通用。它的核心是对于度数大的点和度数小的点采用不同的处理策略。度数小的点出度小枚举开销小度数大的点数量少可以承受更高的单点开销。这种思想在很多图论问题中都有应用比如判断两点是否连通、统计路径数量、图着色等。掌握这个思想比单纯记住三元环计数的代码更有价值。6. 完整代码实现与测试验证6.1 完整代码把上面的所有细节整合起来完整的C实现如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorpairint,int edges; vectorint deg(n1, 0); for (int i 0; i m; i) { int u, v; cin u v; if (u v) swap(u, v); edges.push_back({u, v}); deg[u]; deg[v]; } // 去重 sort(edges.begin(), edges.end()); edges.erase(unique(edges.begin(), edges.end()), edges.end()); m edges.size(); // 重新统计度数去重后 fill(deg.begin(), deg.end(), 0); for (auto [u, v] : edges) { deg[u]; deg[v]; } // 定向建图 vectorvectorint out(n1); for (auto [u, v] : edges) { if (deg[u] deg[v] || (deg[u] deg[v] u v)) { out[u].push_back(v); } else { out[v].push_back(u); } } vectorint mark(n1, 0); long long ans 0; for (int u 1; u n; u) { for (int v : out[u]) { mark[v] u; } for (int v : out[u]) { for (int w : out[v]) { if (mark[w] u) { ans (long long)(deg[u] - 2) (deg[v] - 2) (deg[w] - 2); } } } } cout ans \n; return 0; }6.2 测试用例验证用一个简单的例子来验证假设图中有4个点边为(1,2)、(2,3)、(1,3)、(3,4)。这个图中有一个三元环(1,2,3)。deg[1]2deg[2]2deg[3]3deg[4]1。三元环(1,2,3)贡献的星星数量是(2-2)(2-2)(3-2)1。确实以3为中心连接1、2、4其中1和2已经相连所以星星是3-1-2-4这个结构只有1个。代码输出应该是1。再考虑一个完全图K44个点两两相连。三元环有C(4,3)4个。每个三元环的三个点度数都是3贡献(3-2)×33。总答案应该是4×312。实际验证K4中每个点作为中心可以连接另外3个点其中任意两个外围点都相连所以每个中心贡献C(3,2)3个星星4个中心共12个。代码输出应该是12。6.3 性能测试对于n10⁵m2×10⁵的随机图这个算法的运行时间大约在0.1秒左右。对于n10⁵m10⁶的稠密图运行时间大约在0.5秒到1秒之间。如果时间限制比较紧可以考虑用链式前向星代替vector或者用更快的输入输出方式。7. 一些值得记住的经验教训写这道题的过程中我最大的体会是图论题目的难点往往不在于算法本身而在于对边界情况的处理。三元环计数的定向技巧本身并不复杂但重边、自环、答案溢出、标记数组的初始化这些问题每一个都可能让你WA到怀疑人生。另外一个体会是复杂度分析不能只看最坏情况还要看实际数据的特点。O(m√m)在理论上已经足够优秀但如果实际数据中某些点的出度特别大或者图的结构比较特殊可能还需要针对性地优化。比如如果图中有一个超级节点连接了大量其他点那么这个节点的出度会很大枚举它的出边时开销就会比较高。这时候可以考虑对这个超级节点单独处理或者用bitset来加速判断。最后这道题让我对根号分治有了更深的理解。它的本质是把问题分成两部分一部分规模小但数量多另一部分规模大但数量少分别用适合的方法处理最后合并结果。这种思想在算法设计中非常常见值得反复体会。 
长河君 · 2026/10/16 4:11:45 · 阅读 1.2k 三元环计数与根号分治定向技巧详解
1. 从一道题看三元环计数的本质第一次看到这个题目的时候我盯着Counting Stars这个标题愣了几秒——星星和三元环有什么关系后来把题面读完才反应过来这里的star指的是图论中一种特殊的子图结构一个中心点连接三个外围点外围点之间再互相连边整体看起来像一个三角形外加一根尾巴形状确实有点像简笔画里的星星。而题目要求的是统计一个无向图中所有这样的星星结构数量。这道题的核心难点其实不在星星本身而在于三元环计数——也就是在一个无向图里找出所有三个点两两相连的三角形结构。为什么因为每一个三元环恰好可以贡献三个不同的星星三角形的任意一个顶点作为中心另外两个顶点加上中心自己构成的三元组再配上中心到第三个点的边就形成了一个star。所以整道题的解法可以拆成两步先枚举出图中所有的三元环然后对每个三元环看它的三个顶点各自还能连出去多少条边不包括三角形内部的边把这三个数加起来就是答案。听起来逻辑很清晰但真正动手写的时候问题就来了怎么高效地枚举三元环如果图比较稀疏直接暴力枚举三个点判断是否两两相连复杂度是O(n³)n稍微大一点就超时。如果图比较稠密用邻接矩阵倒是能O(1)判断边是否存在但n³的枚举量依然摆在那里。所以这道题真正考察的是一种经典的三元环计数技巧它能把复杂度压到O(m√m)级别其中m是边数。这个技巧在竞赛圈里有个约定俗成的名字叫按度数定向或者根号分治定向。我第一次接触这个技巧的时候觉得它特别巧妙——它没有用什么高深的算法只是对边做了一个简单的方向约定就把无序的三角形枚举变成了有序的、不重不漏的扫描。下面我就把这个技巧的来龙去脉、实现细节、以及我在实际写题过程中踩过的坑完整地梳理一遍。2. 三元环计数的核心思路给边定一个方向2.1 为什么直接枚举会出问题假设图中有n个点、m条边。最朴素的枚举方式是三重循环遍历所有点对判断是否两两相连。这个复杂度是O(n³)在n1000的时候就是10亿次操作显然不可接受。稍微优化一点可以只枚举存在的边对于每条边(u,v)再枚举u的所有邻居w判断v和w之间是否有边。这样复杂度是O(m·d)其中d是点的平均度数。在最坏情况下比如一个完全图m≈n²/2d≈n复杂度就退化成了O(n³)。问题的根源在于同一个三元环会被重复枚举多次。一个三角形有三条边如果对每条边都做一次枚举邻居再判断的操作这个三角形就会被数到三次。而且更麻烦的是即使我们想办法去重枚举的总量本身也没有减少——每条边都要扫一遍它端点的邻居这个开销是实打实的。2.2 定向的核心思想让每个三元环只被数一次这个技巧的关键洞察是如果我们能给图中的每条边规定一个方向使得每个三元环恰好有一个出度为2的顶点那么我们就可以只从这个顶点出发去枚举三元环做到不重不漏。具体怎么做对于一条无向边(u,v)我们比较u和v的度数如果度数相同就比较编号。规定方向从度数大的点指向度数小的点如果度数相同就从编号大的指向编号小的。这样整个无向图就变成了一个有向无环图因为度数严格递减或者编号严格递减不可能形成环。在这个定向规则下一个三元环(u,v,w)中必然存在一个唯一的顶点它的出度为2——也就是说它同时指向另外两个顶点。这个顶点就是三元环中度数最大或编号最大的那个。于是我们只需要枚举每个点u再枚举u的所有出边指向的点v再枚举v的所有出边指向的点w判断u和w之间是否有边。如果有就找到了一个三元环且这个三元环是以u为出度为2的顶点被唯一发现的。2.3 复杂度分析为什么是O(m√m)这个定向规则下每个点的出度有一个上界。假设一个点u的出度为out(u)那么对于u的每一条出边(u,v)都有deg(u) ≥ deg(v)或者度数相同但编号更大。可以证明out(u) ≤ √(2m)。为什么呢因为u的所有出边指向的点v它们的度数都至少是deg(u)在度数相同的情况下编号更小但度数不会更小。而这些点各自的度数之和至少是out(u)·deg(u)同时这个和不会超过2m所有点的度数之和是2m。所以out(u)·deg(u) ≤ 2m而deg(u) ≥ out(u)因此out(u)² ≤ 2m即out(u) ≤ √(2m)。于是枚举的总复杂度是对每个点u枚举它的出边v总共m条出边再枚举v的出边w每条出边v的出度不超过√(2m)所以总复杂度是O(m√m)。对于m10⁵级别的图m√m大约是3×10⁷完全可以在1秒内跑完。3. 实现细节从建图到统计的完整流程3.1 数据读入与度数统计第一步是读入所有的边同时统计每个点的度数。这里有个细节需要注意题目中的图可能有重边或者自环吗一般来说三元环计数问题中自环不会影响结果因为自环不参与三角形但重边会导致同一个三角形被重复计数。所以稳妥的做法是先去重或者在建图时用set来存储边。不过大多数题目保证没有重边具体要看题面。int n, m; vectorpairint,int edges; vectorint deg(n1, 0); for (int i 0; i m; i) { int u, v; cin u v; edges.push_back({u, v}); deg[u]; deg[v]; }3.2 按定向规则建立有向图接下来根据度数比较规则把每条无向边变成有向边。如果deg[u] deg[v]或者deg[u] deg[v] u v那么方向从u指向v否则从v指向u。vectorvectorint out(n1); // 出边邻接表 for (auto [u, v] : edges) { if (deg[u] deg[v] || (deg[u] deg[v] u v)) { out[u].push_back(v); } else { out[v].push_back(u); } }这里用vectorvector 来存出边邻接表是因为总边数m不算太大vector的动态扩容开销可以接受。如果m特别大比如10⁶可以考虑用链式前向星来节省内存和加快访问速度。3.3 标记数组的使用技巧枚举三元环的时候我们需要快速判断两个点之间是否有边。有两种常见做法一是用哈希表或者set来存边查询O(log m)二是用一个标记数组在枚举u的出边时先把u的所有出边指向的点打上标记然后枚举v的出边w时直接看w是否被标记。第二种做法查询是O(1)的整体更快。vectorint mark(n1, 0); long long ans 0; for (int u 1; u n; u) { // 先标记u的所有出边指向的点 for (int v : out[u]) { mark[v] u; // 用u作为标记值避免每次清空数组 } // 枚举u的出边v再枚举v的出边w for (int v : out[u]) { for (int w : out[v]) { if (mark[w] u) { // 找到一个三元环 u - v - w且u - w // 这里可以统计答案 } } } }这里用mark数组配合u作为标记值是一个很实用的小技巧——避免了每次枚举前都要memset清空数组把清空的开销分摊到了每次赋值上。3.4 统计星星数量的具体计算对于每个找到的三元环(u,v,w)我们需要计算以u、v、w分别为中心时能形成多少个星星。以u为中心为例星星的数量等于u的度数减去2减去三角形内部的两条边u-v和u-w因为u还可以连向其他点每连一个点就多一个星星。所以对于三元环(u,v,w)贡献的星星总数是(deg[u] - 2) (deg[v] - 2) (deg[w] - 2)注意这里的deg是原无向图中的度数不是定向后的出度。因为星星的外围点可以是任意方向上的邻居。if (mark[w] u) { ans (long long)(deg[u] - 2) (deg[v] - 2) (deg[w] - 2); }这里要用long long来存答案因为最坏情况下答案可能达到O(n³)级别int会溢出。4. 那些年我踩过的坑与优化经验4.1 重边导致的重复计数我第一次写这道题的时候没有考虑重边的情况结果WA了好几发。后来发现如果输入中有重边比如u和v之间有两条边那么在定向后out[u]中会有两个vout[v]中会有两个u如果方向是u-v的话。这样在枚举时同一个三元环会被数到多次。解决办法是在读入边的时候用set去重或者在建图前先对边排序去重。sort(edges.begin(), edges.end()); edges.erase(unique(edges.begin(), edges.end()), edges.end());不过要注意去重后m会变小度数统计也要重新做。所以稳妥的流程是先读入所有边到vector排序去重然后再统计度数、建图。4.2 标记数组的初始化问题用mark数组配合u作为标记值确实很巧妙但有一个前提u的值必须是唯一的且不会与之前的标记冲突。如果点的编号是从1到n那么用u作为标记值是完全没问题的因为每次枚举新的u时mark数组中等于u的位置一定是上一次枚举u时留下的而这次枚举会覆盖掉。但如果点的编号有0或者负数就需要额外处理。另外如果n特别大比如10⁶mark数组的内存开销也要考虑不过一般int数组10⁶也就是4MB可以接受。4.3 出边邻接表的遍历顺序在枚举v的出边w时如果out[v]很大遍历开销会比较大。虽然理论上out[v] ≤ √(2m)但在实际数据中某些点的出度可能接近这个上界。一个优化技巧是在枚举u的出边v时如果out[v]的大小加上当前已找到的三元环数量已经超过了某个阈值可以考虑提前终止或者换一种枚举方式。不过对于大多数题目来说直接暴力枚举已经足够快不需要过度优化。4.4 答案溢出的问题这道题的答案可能非常大。假设图是一个完全图n1000那么三元环的数量是C(1000,3)≈1.66×10⁸每个三元环贡献的星星数量大约是3×(n-3)≈3000总答案大约是5×10¹¹远超int的范围。所以必须用long long。我在第一次提交时就是因为用了int结果WA了后来改成long long就过了。4.5 常数优化用数组代替vector如果m比较大比如10⁶vectorvector 的动态扩容和内存碎片可能会成为瓶颈。这时候可以用链式前向星来存图或者用一个一维数组加偏移量来模拟邻接表。具体做法是先统计每个点的出度然后计算前缀和得到每个点在数组中的起始位置最后把边填入数组。这样遍历时是连续内存访问缓存友好速度会快很多。vectorint head(n1, -1), nxt(m), to(m); int cnt 0; auto add_edge [](int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; };这种写法在竞赛中很常见虽然代码稍微复杂一点但在大数据量下性能提升明显。5. 从三元环到更一般的子图计数5.1 四元环计数的类似思路三元环计数的定向技巧可以推广到四元环计数。对于四元环我们可以枚举一条边(u,v)然后枚举u的邻居w和v的邻居x判断w和x之间是否有边。但这样复杂度会高一些。更高效的做法是先按度数定向然后枚举每个点u再枚举u的出边v再枚举v的出边w最后枚举w的出边x判断x是否等于u或者与u相邻。不过四元环的计数要复杂得多因为一个四元环可能被多种方式枚举到需要仔细去重。5.2 三元环计数在实际问题中的应用三元环计数不仅仅是一道竞赛题它在实际中也有很多应用。比如在社交网络分析中三元环也叫三角形是衡量网络聚集系数的重要指标。一个社交网络中三角形越多说明用户之间的关系越紧密社区结构越明显。在推荐系统中如果两个用户有共同的好友即他们和共同好友构成三角形那么他们很可能也认识可以用来做好友推荐。在生物信息学中蛋白质相互作用网络中的三角形结构往往对应着功能模块。5.3 根号分治思想的通用性这道题背后的根号分治思想非常通用。它的核心是对于度数大的点和度数小的点采用不同的处理策略。度数小的点出度小枚举开销小度数大的点数量少可以承受更高的单点开销。这种思想在很多图论问题中都有应用比如判断两点是否连通、统计路径数量、图着色等。掌握这个思想比单纯记住三元环计数的代码更有价值。6. 完整代码实现与测试验证6.1 完整代码把上面的所有细节整合起来完整的C实现如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorpairint,int edges; vectorint deg(n1, 0); for (int i 0; i m; i) { int u, v; cin u v; if (u v) swap(u, v); edges.push_back({u, v}); deg[u]; deg[v]; } // 去重 sort(edges.begin(), edges.end()); edges.erase(unique(edges.begin(), edges.end()), edges.end()); m edges.size(); // 重新统计度数去重后 fill(deg.begin(), deg.end(), 0); for (auto [u, v] : edges) { deg[u]; deg[v]; } // 定向建图 vectorvectorint out(n1); for (auto [u, v] : edges) { if (deg[u] deg[v] || (deg[u] deg[v] u v)) { out[u].push_back(v); } else { out[v].push_back(u); } } vectorint mark(n1, 0); long long ans 0; for (int u 1; u n; u) { for (int v : out[u]) { mark[v] u; } for (int v : out[u]) { for (int w : out[v]) { if (mark[w] u) { ans (long long)(deg[u] - 2) (deg[v] - 2) (deg[w] - 2); } } } } cout ans \n; return 0; }6.2 测试用例验证用一个简单的例子来验证假设图中有4个点边为(1,2)、(2,3)、(1,3)、(3,4)。这个图中有一个三元环(1,2,3)。deg[1]2deg[2]2deg[3]3deg[4]1。三元环(1,2,3)贡献的星星数量是(2-2)(2-2)(3-2)1。确实以3为中心连接1、2、4其中1和2已经相连所以星星是3-1-2-4这个结构只有1个。代码输出应该是1。再考虑一个完全图K44个点两两相连。三元环有C(4,3)4个。每个三元环的三个点度数都是3贡献(3-2)×33。总答案应该是4×312。实际验证K4中每个点作为中心可以连接另外3个点其中任意两个外围点都相连所以每个中心贡献C(3,2)3个星星4个中心共12个。代码输出应该是12。6.3 性能测试对于n10⁵m2×10⁵的随机图这个算法的运行时间大约在0.1秒左右。对于n10⁵m10⁶的稠密图运行时间大约在0.5秒到1秒之间。如果时间限制比较紧可以考虑用链式前向星代替vector或者用更快的输入输出方式。7. 一些值得记住的经验教训写这道题的过程中我最大的体会是图论题目的难点往往不在于算法本身而在于对边界情况的处理。三元环计数的定向技巧本身并不复杂但重边、自环、答案溢出、标记数组的初始化这些问题每一个都可能让你WA到怀疑人生。另外一个体会是复杂度分析不能只看最坏情况还要看实际数据的特点。O(m√m)在理论上已经足够优秀但如果实际数据中某些点的出度特别大或者图的结构比较特殊可能还需要针对性地优化。比如如果图中有一个超级节点连接了大量其他点那么这个节点的出度会很大枚举它的出边时开销就会比较高。这时候可以考虑对这个超级节点单独处理或者用bitset来加速判断。最后这道题让我对根号分治有了更深的理解。它的本质是把问题分成两部分一部分规模小但数量多另一部分规模大但数量少分别用适合的方法处理最后合并结果。这种思想在算法设计中非常常见值得反复体会。