无向图三元环计数
先给每条边定向:由度数小的点连向度数大的点,若度数相等则按编号。
这样一个合法的三元环 \((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)\)。