环计数

· · 个人记录

给定一张无向图 G=(V,E)，求其三元环个数。

考虑给这张图定向。先对 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.