Dyd's Blog

He who has a strong enough why can bear almost any how.

三/四元环计数

Posted on In
Symbols count in article: 3.7k Reading time ≈ 3 mins.

还是比较简单的

三/四元环计数

三元环计数

思考如下问题：

给定一个无向图，求图中有多少个环是由且仅由三个点构成的，这样的环被称为三元环

暴力的办法当然是枚举每一个点 $u$ ，再枚举和它相连的点 $v$ ，再枚举和 $v$ 相连的点 $w$ ，判断 $w$ 是否和 $u$ 相连

但这样会有一个巨大的问题：一个环被算了多遍，必须想办法让一个环只被考虑一遍

考虑将边变为有向边，具体的，对于边 $(u, v), u < v$ ：

  1. 若 $\deg(u) = \deg(v)$ 则令 $v \to u$
  2. 否则，让度数大的指向度数小的

下面证明这样做后原图会变成一个DAG：

使用反证法，假设有一个环为 $a \to b \to … \to a$ ，则有 $\deg(a) \ge \deg(b) \ge … \ge \deg(a)$ ，明显应该 $\deg(a) = \deg(b)$ ，换句话说，这个环上的所有边都是第 $1$ 类情况，那么就有 $a > b > … > a$ 这显然不成立

在上面的DAG中，一个三圆环显然会变成这样：三元环

此时再枚举，这个环就只会被记在红点上了

关于时间，首先我们要枚举每个点和它的出边，时间为 $O(n + m)$ ，然后，要枚举出边指向的点的出边

如此，对于第二次枚举，讨论这个点（就是红色点的出边指向的那个点）的出度：

  1. 如果出度 $\le \sqrt{m}$ ，那么最多有 $n - 1$ 个点会指向它，由它会枚举的点数为就是出度，所以总的时间为 $O(n \sqrt{m})$
  2. 如果出度 $> \sqrt{m}$ ，那么指向它的边最多有 $\frac{m}{\sqrt{m}} = \sqrt{m}$ ，虽然它的出度最坏是 $m$ ，但总的时间为 $O(m\sqrt{m})$

注意在上面的讨论中，第一次枚举和第二次枚举是站在两个不同的角度计算的时间，在计算第二次枚举的时间时，第一次枚举的时间对它并没有影响，故总的时间为 $O(n + m + (n \sqrt{m} 或 m \sqrt{m})) = O(m \sqrt{m})$

同时也可以得到，三元环的个数上界是 $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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define PII pair<int, int>
#define STC static
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int n;
struct Edge
{
    int ne, ver;
} e[M];
int h[N], idx = 0;
bool vis[N];
void add(int x, int y)
{
    e[idx] = {h[x], y}, h[x] = idx++;
}
int find3c()
{
    int res = 0;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = h[x]; i != -1; i = e[i].ne)
            vis[e[i].ver] = true;
        for (int i = h[x]; i != -1; i = e[i].ne)
            for (int j = h[e[i].ver]; j != -1; j = e[j].ne)
                res += vis[e[j].ver];
        for (int i = h[x]; i != -1; i = e[i].ne)
            vis[e[i].ver] = false;
    }
    return res;
}
int main()
{
    int m;
    STC PII _e[M];
    STC int deg[N];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        h[i] = -1;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &_e[i].fi, &_e[i].se);
        if (_e[i].fi < _e[i].se)
            swap(_e[i].fi, _e[i].se);
        ++deg[_e[i].fi], ++deg[_e[i].se];
    }
    for (int i = 1; i <= m; ++i)
    {
        if (_e[i].fi == _e[i].se)
            continue;
        if (deg[_e[i].fi] >= deg[_e[i].se])
            add(_e[i].fi, _e[i].se);
        else
            add(_e[i].se, _e[i].fi);
    }
    printf("%d\n", find3c());
    return 0;
}

四元环计数

简单的思路是将四元环分成两个形如 $u \to v \to w$ 的形式，枚举 $u$ ，然后像三元环化为DAG，一样枚举 $v, w$ ，对于 $u, w$ 记 cnt[u][w] 表示从 $u$ 通过一个其它点到达 $w$ 的路径数，然后对答案的贡献即为 cnt[u][w] * (cnt[u][w] - 1) / 2

这样当然是错误的，因为三元环是无序的，有唯一性（即三个点最多存在一个三元环，且在DAG中这个三元环的形式确定），但四元环就不是了，如图：四元环

同一个四元环在DAG中可能有两种表示（ $2 + 2$ 或者 $3 + 1$ ）

那如何才能不重不漏呢？考虑三元环建边时的不等式：如果存在 $u \to v$ ，则 $\deg(u) \ge \deg(v)$ ，那么，在上面两幅图中，我们发现，度数最大的是同一个点，这启发了我们

我们将每个点按度数大小重新编号，度数相同原来编号大的点在前的方法，就可以通过编号直接得到任意两个点的关系

设重新编号后排名为 $rk$ ，枚举四圆环中 $rk$ 最大的点 $x$ ，再枚举 $x$ 的出点 $y$ ，枚举 $y$ 的出点 $z$ （这里直接枚举无向边，注意判断 $rk(x) > rk(y) > rk(z)$ ）， 这里就得到了一个长度为 $2$ 的链了，再枚举一个点 $c$ ，只要 $rk(x) > rk(c)$ 就计入答案的贡献，不管 $rk(c)$ 和 $rk(z)$ 的关系

时间复杂度还是 $O(m \sqrt{m})$

注意四元环的个数上界是 $nm\sqrt{m}$ ，可能要 long long

代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int n;
struct Edge
{
    int ne, ver;
} e[M << 1];
int h[N], idx = 0;
int id[N], deg[N], rk[N];
int cnt[N];
void add(int x, int y)
{
    e[idx] = {h[x], y}, h[x] = idx++;
}
LL find4c()
{
    LL res = 0;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = h[x]; i != -1; i = e[i].ne)
            if (rk[x] > rk[e[i].ver])
                for (int j = h[e[i].ver]; j != -1; j = e[j].ne)
                    if (rk[x] > rk[e[j].ver])
                        res += cnt[e[j].ver]++;
        for (int i = h[x]; i != -1; i = e[i].ne)
            if (rk[x] > rk[e[i].ver])
                for (int j = h[e[i].ver]; j != -1; j = e[j].ne)
                    cnt[e[i].ver] = 0;
    }
    return res;
}
bool cmp(int x, int y)
{
    return deg[x] == deg[y] ? x < y : deg[x] < deg[y];
}
int main()
{
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        h[i] = -1, id[i] = i;
    for (int i = 1, u, v; i <= m; ++i)
    {
        scanf("%d%d", &u, &v);
        ++deg[u], ++deg[v];
        add(u, v), add(v, u);
    }
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= n; ++i)
        rk[id[i]] = i;
    printf("%lld\n", find4c());
    return 0;
}

拓展

以后在写，现在鸽了

废话

啊啊啊，马上就要考期末考试了，这估计是我考前最后一次写blog了，老天保佑我别考爆炸啊！