三元环_判断平面图中是否存在三元环

Problem

给出$n$个点$m$条边的无向图，找出图中所有长度为$3$的环。

Solution

根据原图计算每个点的度数，然按以下规则将图转为有向图：
对于原图中一条边，如果两个端点的度数不相等，则度数大的点指向度数小的点。否则，标号大的点指向标号小的点。
将图转换成有向图后，枚举每个点$a$，枚举$a$指向的每个点$b$，枚举$b$指向的每个点$c$，判断点$a$和$c$之间是否有边，如果有，则构成一个三元环，否则不构成三元环。

正确性证明

首先，若将图中的结点按度数为第一关键字，标号为第二关键字排序，则总是小的结点向大的结点连边，故图为一个有向无环图。
其次，对于原图中的一个三元环，也可以按上述方式排序，设排序后三元环的点按顺序排列依次为$a,b,c$，则在有向无环图中其对应有唯一一条路径$a\Rightarrow b\Rightarrow c$，从而每个三元环都会被枚举到且仅被枚举一次。

时间复杂度

对于一个度数大于$\sqrt{m}$的点，它指向的点最多$\sqrt{m}$个，这样的点最多$\sqrt{m}$个，故当第二个点度数大于$\sqrt{m}$时枚，举的三元组数量不多于 $m\sqrt{m}$个。
对于度数小于$\sqrt{m}$的点，显然当它们都在$\sqrt{m}$个点的完全图中的时候三元环数量最多，而这样的图中的三元组数量也不多于$m\sqrt{m}$个。
故以上算法的时间复杂度为$O(m\sqrt{m})$。

[SDOI2018]旧试题

求${\sum }_{i=1}^A{\sum }_{j=1}^B{\sum }_{k=1}^{C}d(ijk)$，$d(ijk)$为$i\ast j\ast k$的因子数。
令$I(x)=[x=1],(\ast )=\lfloor \frac{A}{d1}\rfloor \lfloor \frac{B}{d2}\rfloor \lfloor \frac{C}{d3}\rfloor ,(\ast \ast )=u(x)u(y)u(z)$
$$\begin{gathered} \sum _{i=1}^A\sum _{j=1}^B\sum _{k=1}^{C}d(ijk)= \\ \sum _{i=1}^A\sum _{d1|i}\sum _{j=1}^B\sum _{d2|j}\sum _{k=1}^C\sum _{d3|k}I((d1,d2))I((d2,d3))I((d1,d3))= \\ \sum _{d1=1}^A\sum _{d2=1}^B\sum _{d3=1}^C\lfloor \frac{A}{d1}\rfloor \lfloor \frac{B}{d2}\rfloor \lfloor \frac{C}{d3}\rfloor I((d1,d2))I((d2,d3))I((d1,d3)) \\ =\sum _{d1=1}^A\sum _{d2=1}^B\sum _{d3=1}^C(\ast )\sum _{x|(d1,d2)}u(x)\sum _{y|(d2,d3)}u(y)\sum _{z|(d1,d3)}u(z) \\ =\sum _{x=1}^{min(A,B)}\sum _{y=1}^{min(B,C)}\sum _{z=1}^{min(A,C)}u(x)u(y)u(z) \\ \sum _{x|d1,z|d1}\lfloor \frac{A}{d1}\rfloor \sum _{x|d2,y|d2}\lfloor \frac{B}{d2}\rfloor \sum _{y|d3,z|d3}\lfloor \frac{C}{d3}\rfloor \\ =\sum _{x=1}^{min(A,B)}\sum _{y=1}^{min(B,C)}\sum _{z=1}^{min(A,C)}u(x)u(y)u(z) \\ \sum _{lcm(x,z)|d1}\lfloor \frac{A}{d1}\rfloor \sum _{lcm(x,y)|d2}\lfloor \frac{B}{d2}\rfloor \sum _{lcm(y,z)|d3}\lfloor \frac{C}{d3}\rfloor \\ =\sum _{x=1}^{m(A,B)}\sum _{y=1}^{m(B,C)}\sum _{z=1}^{m(A,C)}(\ast \ast )f([x,z],A)f([x,y],B)f([y,z],C) \end{gathered}$$
其中$f(n,m)=\sum _{i=1}^{n\ast i\le m}\lfloor \frac{m}{n\ast i}\rfloor$，可以预处理，$[x,y]=lcm(x,y)$。
特别地，当$n>m$时$f(n,m)=0$。
故对于枚举的$x,y,z$，需要满足$[x,z]\le A,[x,y]\le B,[y,z]\le C$且$u(x)u(y)u(z)\ne 0$才对答案有贡献。
建一张$n(n=max(A,B,C))$个点的图，对于点$a,b$，如果$u(a)u(b)\ne 0$则在点$a$和点$b$之间连一条边权为$lcm(a,b)$的边，问题转换对于这张图中所有的三元环计算上式。采用上述三元环算法即可。
关于建图：枚举$lcm$，根据莫比乌斯函数的性质，如果$u(lcm)=0$则略过，否则枚举$lcm$的因子连边即可（根据实测，在$A,B,C\le 1e5$的情况下边数在$7e5$左右）。