「学习笔记」找出无向图中的三元环

题目大意

给定一个 $n$ 个点 $m$ 条边的无向图，要求找到图中所有的三元环。

数据范围：$n \le 5 \times 10^4, m \le 2 \times 10^5$。

算法流程

一个 $m$ 条边的无向图中最多有 $O(m \sqrt m)$ 个三元环。本文介绍一种 $O(m \sqrt m)$ 求所有三元环的算法。

先考虑将所有无向边定向，使得所有边的起点度数不小于终点度数，且定向后的图形成一个 DAG。一种合法的定向方法是：对于一条边联结的两个结点，如果他们的度数不同，则只有一种定向方案；如果他们的度数相同，那么就从编号较小的点连向编号较大的点。容易发现构造出的方案是合法的。

我们发现，在一个 DAG 上的三元环一定是一个点向外连两条边，然后另一条边方向任意。也就是说对于三元环 $(u, v, w)$，一定可以重新排列结点，使得边 $(u, v), (u, w), (v, w)$ 存在，并且只有一种排列方式。

然后找三元环算法正式开始。对于每个结点 $u$，我们先将它可以一步走到的结点打上标记。然后，我们枚举 $u$ 可以一步走到的节点 $v$，再枚举 $v$ 可以一步走到的节点 $w$，最后看 $w$ 是否被 $u$ 标记过。如果标记过，则我们找到了一个三元环。由于上一段提到三元环的性质，不难发现这种算法不会重复，不会遗漏。

下面我们来证明该算法的复杂度。我们记每个点的入度为 $\text{in}(i)$，出度为 $\text{out}(i)$，度数为 $\text{deg}(i)$，那么有：$\sum_{u} \text{in}(u) = m, \sum_{u} \text{out}(u) = m, \sum_{u} \text{deg}(u) = 2m$。

该算法的枚举次数等于 $\sum_{u} \sum_{(u, v) \in E} \sum_{(v, w) \in E} 1$，如果我么枚举 $(u, v)$ 的话，它就等于 $\sum_{(u, v) \in E} \text{out}(v)$。

我们根据 $\text{out}(v)$ 分类讨论：

• 如果 $\text{out}(v) \le \sqrt m$，那么 $\sum_{(u, v) \in E} [\text{out}(v) \le \sqrt m]\text{out}(v) \le \sum_{(u, v) \in E} \sqrt m = m \sqrt m$。
• 如果 $\text{out}(v) > \sqrt m$，那么 $\text{deg}(u) \ge \text{deg}(v) \ge \text{out(v)} > \sqrt m$。因为 $\sum_{u} \text{deg}(u) = 2m$，所以这样能一步到达 $v$ 的 $u$ 不会超过 $\sqrt m$ 个。同时因为 $\sum_{u} \text{out}(u) = m$，所以 $\sum_{(u, v) \in E} \text{out}(v) \le m \sqrt m$。

所以算法的复杂度得到了保障。

另外我们注意到 $\sum_{(u, v) \in E} \text{out}(v) = \sum_{u} \text{in}(u) \times \text{out}(u) = \sum_{(u, v) \in E} \text{in}(u)$，所以我们将所有边反向后是不改变复杂度的。也就是说我们也可以从度数小的点向度数大的点连边，复杂度也是 $O(m \sqrt m)$ 的。

代码实现

#include <cstdio>