环计数

考虑给这张图定向。先对 $G$ 中的节点排序，度数小的排在度数大的前面，如果度数相同则按编号排序，即 $\text{deg}_i<\text{deg}_j\lor (\text{deg}_i=\text{deg}_j\land i<j)\Longrightarrow rk_i<rk_j$。

考虑强制 $rk_i$ 小的向 $rk_i$ 大的连边，令新图为 $G'=(V',E')$，可以发现，原图中的三元环 $(A,B,C)$（钦定 $rk_A<rk_B<rk_C$）在 $G'$ 中只有一种可能：$A\to B,A\to C,B\to C$。

然后这个直接枚举 $A\to B,B\to C$ 看是否存在 $A\to C$ 就可以。复杂度 $O(|E|\sqrt{ |E|})$。

接下来是时间复杂度证明。

显然判定可以做到 $O(1)$，而判定的次数为 $\sum\limits_{(u,v)\in E'}\sum\limits_{w}[(v,w)\in E']$。

令 $\text{out}_i$ 表示 $G'$ 中点 $i$ 的出度。显然左边那一部分枚举次数是 $O(|E|)$ 的，只需要证明 $\text{out}_v$ 是根号级别的就行。

定义 $S_u$ 为 $v\mid (u,v)\in E'$。显然根据 $G'$ 连边的方式，有 $\forall i\in S_u,\text{out}_u\le\text{deg}_u\le\text{deg}_i$。

根据度数的性质 $\text{out}_u\cdot \text{out}_u\le\sum\limits_{i\in S_u} \text{deg}_i\le 2|E|$。最左边是 $\deg_i$ 都取到 $\text{out}_u$ 的情况。

则 $\text{out}_u\le \sqrt{2|E|}$。

板子题 P1989。

接下来是求四元环个数。

和前面一样，我们对原图定向，构造 $G'$。此时原图中四元环 $(A,B,C,D)$（同样钦定 $rk_A<rk_B<rk_C<rk_D$）在 $G'$ 中有三种可能：

我们令 $f_A$ 表示 $A\to B\to C$ 的路径数量，$g_A$ 表示 $A\gets B\to C$ 的数量。

显然 $f_A$ 是可以 $O(|E|\sqrt{|E|})$ 求的。

对于 $g_A$，考虑建立 $G'$ 的反图 $G''$，枚举 $(u,v)\mid (u,v)\in E''$，和 $(v,w)\mid (v,w)\in E'$ 即可。复杂度同样 $O(|E|\sqrt{|E|})$。因为对于 $v$，枚举 $(v,w)$ 为 $\text{out}_v$，不超过 $\sqrt{2|E|}$，枚举 $(u,v)\in E''$ 是 $O(|E|)$ 的。

对于（1），方案数为 $\sum\limits_{B}f_B\cdot g_B$，对于（2），方案数为 $\sum\limits_{A}\binom{f_A}{2}$，对于（3），方案数为 $\dfrac{\sum\limits_{C}\binom{g_C}{2}}{2}$。这里除以 $2$ 是因为选择 $C$ 和选择 $D$ 都会计算一遍。

板子题 LibreOJ P191.

P9850 [ICPC 2021 Nanjing R] Ancient Magic Circle in Teyvat

gugugu.