无向图三元环计数（根号算法）

根号算法）"/>

无向图三元环计数（根号算法）

题目描述

         给定一个 n n n 个点， m m m 条边的简单无向图，求其三元环个数。 1 ≤ n ≤ 1 0 5 ， 1 ≤ m ≤ 2 × 1 0 5 1 \leq n \leq 10^5，1 \leq m \leq 2 \times 10^5 1≤n≤105，1≤m≤2×105。 保证图没有 重边 和 自环。但是不保证图联通。

分析：

暴力：

         我们考虑暴力该怎么做。注意到边数没有达到 n 2 n^2 n2 级别，而是跟 n n n 同阶，我们考虑枚举边。
         我们枚举一条边，设这条边连接了两个点 u u u， v v v。那么我们再枚举一个点 k k k， O ( 1 ) O(1) O(1) 的去判断是否存在边 ( u , k ) (u, k) (u,k) 和 ( v , k ) (v, k) (v,k)。时间复杂度 O ( m n ) O(mn) O(mn)。
         但是这样做好像会有点浪费，因为如果 k k k 至少和其中任何一个点连接才有枚举的价值。我们可以考虑枚举 u u u 或者 v v v 的所有连边，不妨枚举 u u u 的所有连边，如果某一条连边所连接的点是 k k k，那么我们再 O ( 1 ) O(1) O(1) 的判断是否有 ( k , v ) (k, v) (k,v) 这条边。 时间复杂度是 O ( m 2 ) O(m^2) O(m2)。
         我们接着考虑，如果我们每次枚举点 u u u 是 u , v u,v u,v 两个点中度数较小的那个，会不会能够很大的提高效率呢？ 如果 u u u 是 u , v u,v u,v 中度数较小的那个，设 u u u 的度数为 d e g u deg_u degu​。
         如果 d e g u ≤ m deg_u \leq \sqrt{m} degu​≤m ​，那么很显然 m × m m \times \sqrt{m} m×m ​ 不会超时。
         如果 d e g u ≥ m deg_u \geq \sqrt{m} degu​≥m ​ 那么就意味着 d e g v ≥ m deg_v \geq \sqrt{m} degv​≥m ​。我们考虑到所有点的度数之和为 2 m 2m 2m，所以度数超过 m \sqrt{m} m ​ 的点的数量小于 m \sqrt{m} m ​ 个。首先因为没有重边，所以 n 2 ≥ m n^2 \geq m n2≥m。所以 n ≥ m n \geq \sqrt{m} n≥m ​。并且每个点的度数小于等于 n n n。 我们想让所有点的度数都平均的尽可能大，考虑极端数据就是 m \sqrt{m} m ​ 个点，每一个点的度数都是 m + 1 \sqrt{m} + 1 m ​+1 的完全图，我们考虑在这种情况下复杂度是 O ( m m ) O(m \sqrt{m}) O(mm ​) 的也不会超时。至于那种想让某几个点度数很大，其他点度数很小的菊花图，我们发现也只会在枚举个别边的时候复杂度会比较高，其他情况还是很小的。所以也超时不了。
         这样做好像可行了，应该能拿到不少的分了。

正解：

         我们把无向图变成 有向图，给每个边加一个方向。
         加方向的规则是，对于一条边 ( u , v ) (u,v) (u,v) 而言，我们让其由度数小的点指向度数大的点。如果度数一样，就让编号小的点指向编号大的点。
         具体来讲， u → v u \to v u→v 的条件是 d e g u < d e g v deg_u < deg_v degu​<degv​ 或者 d e g u = d e g v deg_u = deg_v degu​=degv​ 并且 u < v u < v u<v。
         我们发现，在这样的条件下，形成的有向图 一定无环，可以把连边规则看作是优先级，那么有向边就是某一组优先关系，所以一定不会存在环。 进一步，我们发现，原图中的所有环一定等价于所有的形如 u → v u \to v u→v， u → k u \to k u→k， v → k v \to k v→k 的三元关系。我们只要找出来所有这样的三元关系就好了。
         方法是我们枚举一个点 u u u 的所有出边，并且把所有出点 v v v 打上时间戳为 u u u 的标记。然后枚举所有 v v v 的出边，如果有一个出点 k k k 的时间戳是 u u u，那么让答案加1。这样做等价于 以每一个点作为环中优先级最低的点，找出所有这样的环的数量。所以是不重不漏的。

         我们来分析复杂度。
         首先就是任意一个点的出度不会超过 m \sqrt{m} m ​。因为如果一个点在原图中的度数小于 m \sqrt{m} m ​，那么在有向图上它都出度不会超过原图上的度数。所以小于 m \sqrt{m} m ​。
         如果一个点在原图中的度数大于 m \sqrt{m} m ​，但是连边的条件是度数小的点朝度数大的点连边，因为总边数为 m m m，所以度数大于 m \sqrt{m} m ​ 的点不会超过 m \sqrt{m} m ​ 个，因此这个点的出度也不会超过 m \sqrt{m} m ​。
         每一个点对复杂度的贡献是 I n i × O u t i In_{i} \times Out_i Ini​×Outi​， I n i In_i Ini​ 是 i i i 号点的入度， O u t i Out_i Outi​ 是 i i i 号点的出度。因为 O u t i Out_i Outi​ 是 m \sqrt{m} m ​ 量级，而 ∑ i = 1 n I n i = m \sum_{i = 1}^{n} In_i = m ∑i=1n​Ini​=m。所以总复杂度是 O ( m × m ) O(m \times \sqrt{m}) O(m×m ​)。

CODE：

#include<bits/stdc++.h>
#define N 100100
#define M 200100
#define pb push_back
#define LL long long
using namespace std;
int n, m, u[M], v[M], deg[N], tim[N];
vector< int > E[N];
LL res;
int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++){scanf("%d%d", &u[i], &v[i]);deg[u[i]]++; deg[v[i]]++;}for(int i = 1; i <= m; i++){if(deg[u[i]] != deg[v[i]]){if(deg[v[i]] > deg[u[i]]) swap(u[i], v[i]);E[v[i]].pb(u[i]);//每一个里面放比它度数大的 }else{if(u[i] > v[i]) swap(u[i], v[i]);E[u[i]].pb(v[i]);}}for(int u = 1; u <= n; u++){for(auto v : E[u]){// 扫描出边， 复杂度O（m） tim[v] = u;}for(auto v : E[u]){for(auto x : E[v]){//扫描出边的出边，每一条边会被扫到一次，一个边贡献√m的复杂度，所以总复杂度是O（m√m） 的 if(tim[x] == u) res++; }}}printf("%lld\n", res);return 0;
}