当前位置: 首页 > news >正文

无向图三元环计数 小记

无向图三元环计数

先给每条边定向:由度数小的点连向度数大的点,若度数相等则按编号。

这样一个合法的三元环 \((x,y,z)\) 一定形如 \(x\to y,x\to z,y\to z\)

考虑枚举 \(x\),把所有 \(z\) 打上标记,再枚举 \(y\)\(y\) 的出边 \(w\),统计 \(w\) 被打上标记的个数。复杂度其实是 \(O(m\sqrt m)\) 的。

证明:

  • 对于度数小于等于 \(\sqrt m\)\(y\),枚举 \(w\) 的复杂度为显然 \(O(m\sqrt m)\)
  • 而对于度数大于 \(\sqrt m\)\(y\)由于其只能向度数不小于它的点连边,而度数和是 \(O(m)\) 的,所以其只能连 \(O(\sqrt m)\) 个点,这部分枚举 \(w\) 的复杂度也是 \(O(m\sqrt m)\),因此总复杂度就是 \(O(m\sqrt m)\)
http://www.hskmm.com/?act=detail&tid=25053

相关文章:

  • Python语法基础篇(含有类型转换、拷贝、可变对象/不可变对象,函数,拆包,异常,模块,闭包,装饰器)
  • 2025 年探伤仪厂家最新企业品牌推荐排行榜,涡流探伤仪,超声波探伤仪,管材探伤仪,焊缝探伤仪,无损探伤仪推荐这十家公司!
  • 2025 年建筑工程施工总包最新推荐排行榜,以严格质量管控彰显行业实力推荐这十家公司!
  • 与斐波那契数列相关的对换题目 CF553B Kyoya and Permutation
  • wpf .net 8 使用mvvm指南
  • office办公软件
  • 2025.10.4训练记录
  • st表 + 变形的djs (好题
  • 2025年微信小程序开发:AR/VR与电商的最新案例 - 指南
  • 10.5
  • 在wpf .net 8项目中使用materialDesign 4 以上版本的的注意事项
  • 学习STC51单片机26(芯片为STC89C52RCRC) - 实践
  • 洛谷P14120 题解 - lemon
  • cf41d
  • 33 ACwing 294 Count The Repetitions 题解
  • 电赛电装实习总结
  • 30 ACwing 291 蒙德里安的梦想 题解
  • 21 ACwing 289 环路运输 题解
  • 26 UVA1630 串折叠 Folding 题解
  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四