图论，根号算法-三/四元环计数

记录度数，度数大的指向度数小的。度数相同的话编号大的指向编号小的。就原图变成一个DAG了。无环是显然的。

然后对于每个点X，将出边记录下来,打标记。再对于X的出边的点，枚举出边，看是否是 X的出边的点。是的话就计数。

$O(m\sqrt{m})$

考虑任意一个三元环 $(a,b,c)$ ,经过转换之后它一定长这样(想想为什么?),所以所有环都会被记录一次且仅一次。

复杂度来源于两个部分：一。枚举出边二.枚举出边的出边.

一部分复杂度显然为: $\text{[math]}$

第二部分的复杂度：

$1.当点的出度 < \sqrt{m}时，指向它的点最多n个。那么复杂度最坏为 n * \sqrt{m}$

$1.当点的出度 > \sqrt{m} (最多是m)时，指向它的点的个数只有 \frac{m}{\sqrt{m}} =\sqrt{m}个。那么这个部分复杂度最坏为 m * \sqrt{m}$

延续三元环计数的思想。一个四元环是两个长度为2的路径拼接而成.

我们将每个点按度数大小重新编号,保证每个编号不同,i的编号大小为rk[i]. 对于每个u,枚举出边点v。然后对于每个 v，枚举所有 rk[w] > rk[v] 的点，若 rk[w] > rk[u]同时成立。那么 ans[u] += cnt[w],cnt[w]++;

注：为什么不沿用之前的算法。直接对度数建边呢？因为我们不仅要知道 v 和 w的关系，还要知道 u和 w的关系.所以直接重新编号，就可以对于任意两个点，直接比较了。

$O(m\sqrt{m})$

其实我们可以发现上述过程， ① cnt[w]是w的入度 ② w 的 rk 在 u , v , w中是最大的，而 u 的 rk 是最小的。那么当有两组"长度为2的不同路径" $(u,v_i,w) 和 (u,v_j,w)$ 那么代表着我们找到了一个四元环.

考虑对于任意一个四元环 $(u,v_i,v_j,w)$ .虽然环有对称性，但是经过这样处理后贡献一定只会从 u 计算到 w上。

$对于长度为2的路径 u \rightarrow v \rightarrow w.当找到 book[w] == true. ans[u \rightarrow v]++ , ans[w \rightarrow v]++$

$但是对于长度为1的路径 u \rightarrow w. 由于这是一条汇边。所以需要开个桶cnt[w]统计 w 被到达多少次。那么 ans[u \rightarrow v] += cnt[w].$

*记得cnt 和 book 一样一起被清空.

暂时想不出好方法.

考虑一个三元环: $(u,v,w)$ . 若book[w] = true. 那么 ans[v]++. ans[w]++(这个再最后再加，防止重复计数,u,w是汇点嘛). 然后 u 加上所有 w 使得 book[w] = true 的个数.

考虑对于任意一个四元环 $(u,v_i,v_j,w)$ , 以及入度cnt[w].

$\text{[math]}$ 解释:通过画图我们可以理解成: 对于在环边上的 v(非汇点) ,我们可以和 [除了它本身以外所有的以w为结尾的 “长度为2的路径”] 构成四元环

$\text{[math]}$ . 解释:它们实际上是汇点。我们可以从cnt[w]个入边中随便选两个"长度为2的路径"，都可以构成四元环.

1.https://www.cnblogs.com/Khada-Jhin/p/10143074.html

2.https://www.cnblogs.com/wzxbeliever/p/11792340.html
3.https://www.luogu.com.cn/blog/i207M/san-yuan-huan-ji-shuo-xue-xi-bi-ji