求无向图中的三元环个数_枚举三元环

无向图是个稀疏图，点数$n<10^5$, 边数$m<min(10^5, \frac{n*(n - 1)}{2})$.现在给出$n, m,E(边的集合)$。求出这个无向图中三元环的个数，两个三元环不同是：当对于两个三元环的边，某个三元环存在一条边在另一个三元环的边中无法找到！

首先想到的方法只能是暴力求解，很直接的暴力就是枚举每一条边，以一条边度数小的端点再枚举另一条边，然后看看第一条边的起始点和第二条边的终点之间是否存在一条边，最后答案除3。复杂度$O(m*\sqrt{m})$。当然这是不判重的写法，判重的话能复杂度能降到$O(\frac{m*\sqrt{m}}{3})$。

这里介绍一种复杂度看起来比$O(m*\sqrt{m})$高但实际上复杂度还是$O(m*\sqrt{m})$的暴力方法但是实际上可以减少很多不必要的判断的方法。首先设想一种理想情况，也就是这个图有$x$个点且是个完全图(每两个点都有边相连， 也就是说从一个点发出的任意两条边都可以构成元环)，那么这个图的边数就是$\binom{2}{x} = m, x = \sqrt{m}$，但是题目中的点是$n$, 那么就有一些点的度大于$x$或者小于$x$，我们考虑先考虑小于或等于$x$的点，这些点我们就暴力枚举，它们向度数大于$x$的点连边或者同样向度数小于$x$的点连边；然后考虑度数大于$x$的点，前面已经暴力枚举过小于$x$的点向大于$x$的点连边了，那么对于大于的点，我们就在这些点集的内部暴力枚举两两连边。这样这个算法就完成了。

复杂度分析：

对于第一类点的三元环，由于枚举的时候是从一个点出发枚举两条边，而这个点的度又是小于$x$的，所以一条边最多被枚举$x$次，而最多会枚举$m$条边，所以第一类点的复杂度是$mx$。

对于第二类点的三元环，第二类点最多也就$x$个，所以枚举集合中的三个点复杂度是$x^3$。

所以最终复杂度还是$O(m*\sqrt{m})$。

注意，由于hash的时候我用的是set，超时了。set是用红黑树写的，所以查找的复杂度是$O(\log{n})$，因此我们可以用常数优化，自己手写hash，或者使用C++11的新特性–unordered_set，unordered_set使用hash表实现的，因此查找的复杂度是$O(1)$，同样的，用unordered_set就不能保证是有序的，不过在这里没关系。

下面我贴出两种暴力的方法代码吧(第一种在3ms的时限下超时，第二种过了)。

一：

#include <stdio.h>
#include <string.h>

#include <tr1/unordered_set>

using namespace std;

using namespace std::tr1;

#define MAX_LINE 100005

typedef long long LL;

typedef struct tagEdge {
    LL src, des, next;
}Edge;

Edge e[MAX_LINE * 2];
int head[MAX_LINE];
int num_e;

int D[MAX_LINE];

int n, m;

unordered_set<LL> st;
unordered_set<LL> used;

void add_edge(int src, int des)
{
    e[num_e].src = src;
    e[num_e].des = des;
    e[num_e].next = head[src];
    head[src] = num_e++;
}

void ssort(LL &s, LL &m, LL &d)
{
    LL tmp = s + m + d;
    LL ts = min(min(s, m), d);
    LL td = max(max(s, m), d);
    s = ts, d = td, m = tmp - s - d;
}

LL work()
{
    LL ans = 0;
    for (int i = 0; i < num_e; i++) {
        if (!(i & 1) && D[e[i].des] > D[e[i + 1].des])
            continue;
        int src = e[i].src, des = e[i].des;
        for (int j = head[des]; j + 1; j = e[j].next) {
            if (e[j].des == src)
                continue;
            LL sss = src, mmm = des, ddd = e[j].des;
            ssort(sss, mmm, ddd);
            if (st.find(sss * MAX_LINE * MAX_LINE + mmm * MAX_LINE + ddd) != st.end())
                continue;

            LL ss = src;
            LL dd = e[j].des;
            if (ss > dd)
                swap(ss, dd);
            if (st.find(ss * MAX_LINE + dd) != st.end())
                ++ans, st.insert(sss * MAX_LINE * MAX_LINE + mmm * MAX_LINE + ddd);
        }
    }
    return ans;
}

int main()
{
    int T;
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &n, &m);
        memset(head, -1, sizeof(head));
        memset(D, 0 , sizeof(D));
        num_e = 0;
        st.clear();
        used.clear();

        LL src, des;
        for (int i = 0; i < m; i++) {
            scanf("%lld%lld", &src, &des);
            ++D[src], ++D[des];
            if (src > des)
                swap(src, des);
            st.insert(src * MAX_LINE + des);
            add_edge(src, des),
            add_edge(des, src);
        }

        printf("%lld\n", work());
    }
    return 0;
}

/**************************************************************
    User: FlushHip
    Language: C++
    Result: 时间超限
****************************************************************/
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

二：

#include <stdio.h>
#include <string.h>
#include <math.h>

#include <tr1/unordered_set>
#include <vector>

using namespace std;

using namespace std::tr1;

#define MAX_LINE 100005

typedef long long LL;

int D[MAX_LINE];

int n, m;

unordered_set<LL> st;
vector<int> e[MAX_LINE];
vector<int> dy;

int main()
{
    int T;
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &n, &m);
        memset(D, 0 , sizeof(D));
        st.clear();
        dy.clear();
        for (int i = 0; i < MAX_LINE; i++)
            e[i].clear();

        int src, des;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &src, &des);
            ++D[src], ++D[des];
            st.insert(1LL * src * MAX_LINE + des);
            st.insert(1LL * des * MAX_LINE + src);
            e[src].push_back(des);
            e[des].push_back(src);
        }

        LL ans = 0;

        int top = sqrt((double)m);

        for (int i = 1; i <= n; i++)
            if (D[i] <= top) {
                for (int j = 0; j < e[i].size(); j++)
                    if (D[e[i][j]] > top || e[i][j] >= i)
                        for (int k = j + 1; k < e[i].size(); k++)
                            if (D[e[i][k]] > top || e[i][k] >= i)
                                if (st.find(1LL * e[i][j] * MAX_LINE + e[i][k]) != st.end())
                                    ++ans;
            } else {
                dy.push_back(i);
            }

        for (int i = 0; i < dy.size(); i++)
            for (int j = i + 1; j < dy.size(); j++)
                if (st.find(1LL * dy[i] * MAX_LINE + dy[j]) != st.end())
                    for (int k = j + 1; k < dy.size(); k++)
                        if (st.find(1LL * dy[i] * MAX_LINE + dy[k]) != st.end() &&
                            st.find(1LL * dy[k] * MAX_LINE + dy[j]) != st.end())
                            ++ans;

        printf("%lld\n", ans);
    }
    return 0;
}

/**************************************************************
    Problem: 1187
    User: FlushHip
    Language: C++
    Result: 正确
    Time:2572 ms
    Memory:15332 kb
****************************************************************/
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81