主要记录一些平时见到的比较巧妙的tirck。
无向图三元环计数
做法：按照节点度数从小到大枚举每个点 \(i\)，然后枚举与之相连的点 \(x\)，再枚举与 \(x\) 相连的点 \(y\)，如果 \(y\) 与 \(i\) 有连边且这三个点度数递增即合法。
复杂度分析：
下文默认 \(n\)，\(m\) 同阶。
考虑根号分治，将点分为度数大于 \(\sqrt n\) 和度数小于等于 \(\sqrt n\) 两类。
-
\(x\) 出度数小于 \(\sqrt n\)，那么 \(y\) 就最多只有 \(\sqrt n\) 个，由于 \(x\) 可能被所有点枚举到，所以这一部分时间复杂度是 \(\operatorname{O}(n\sqrt n)\)
-
\(x\) 出度数大于 \(\sqrt n\)，那么这样的 \(x\) 只有 \(\sqrt n\) 个，且因为只会去找度数比其大的点，所以时间复杂度 \(\operatorname{O} (n\sqrt n)\)。
于是我们就在 \(\operatorname{O} (n \sqrt n)\) 的时间复杂度内解决了这个问题
标签：度数,记录,复杂度,sqrt,trick,枚举,经典,operatorname From： https://www.cnblogs.com/caoshurui/p/18339647