DDOSvoid's Blog

三元环计数

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

简介

简单无向图三元环计数

首先我们将无向边变成有向边，我们将所有边的方向改为度数小的连向度数大的点

这样每个点的度数不会超过 $O(\sqrt m)$，因为原图度数大于 $O(\sqrt m)$ 的点只会连向度数更大的点，而度数更大的点不会超过 $O(\sqrt m)$

然后我们注意到一个三元环的样子应该是 $u\rightarrow v,u\rightarrow w,v\rightarrow w$

我们只需要枚举 $u\rightarrow v$ 这条边，然后枚举 $v$ 的所有出边即可

时间复杂度 $O(m\sqrt m)$，同时这也告诉我们答案的界大概就是这个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100010
#define maxm 200010
#define ll long long 
using namespace std;

int n, m, x[maxm], y[maxm], du[maxn]; 

struct Edge {
    int to, next;
} e[maxm]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int ans, vis[maxn]; 
int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> x[i] >> y[i], ++du[x[i]], ++du[y[i]];
    for (int i = 1; i <= m; ++i) {
        int u = x[i], v = y[i];
        if (du[u] > du[v] || du[u] == du[v] && u > v) swap(u, v);
        add_edge(u, v); 
    }
    for (int u = 1; u <= n; ++u) {
        for (int i = head[u]; ~i; i = e[i].next) vis[e[i].to] = u;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            for (int j = head[v]; ~j; j = e[j].next)
                if (vis[e[j].to] == u) ++ans;
        }
    } cout << ans << "\n"; 
    return 0;
}

有向图三元环计数

我们将边看成无向边，然后按照简单无向图三元环计数的方法跑一遍

对于每个枚举到的三元环都判断一下这三条边是否能形成一个三元环即可

竞赛图三元环计数

注意到不是三元环的一个三元组一定是形如 $u\rightarrow v,u\rightarrow w,v\rightarrow w$

我们考虑用所有的三元组减掉一定不合法的三元组

那么答案就是 $\binom{n}{3}-\sum_{i=1}^n\binom{out_i}{2}$

其中 $out_i$ 为点 $i$ 的出度

简单无向图四元环计数

还是考虑给边定向

然后我们会发现，四元环 $(a,b,c,d)$ 有多种形态

但最重要的是，不妨设度数最大的点是 $d$

那么一定有 $$ 和 $$

那么 $b$ 和 $a$ 以及 $c$ 之间的关系式不确定的

那么我们暂时不定向，而是枚举 $$，然后枚举 $$，这里枚举的 $d$ 的度数要保证大于 $b$ 和 $a$

这样就可以统计答案，并且不会有重复

代码坑