P1989 无向图三元环计数

P1989 无向图三元环计数

将每条边定向，由度数小的指向度数大的。然后统计答案，复杂度为所有点入度乘出度的和。对于度数 $ \le O(\sqrt m)$ 的点，出度最多为 $O(\sqrt m)$ ，入度和最多为 $O(m)$ ，复杂度 $O(n \sqrt m)$ ；对于度数 $\ge O(\sqrt m)$ 的点，由于所有点度数和为 $O(m)$ ，所以出度最多为 $O(\sqrt m)$ ，入度和最多为 $O(\sqrt m)$ 。故复杂度 $O(m \sqrt m)$ 。

查看代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;
PII e[M];
bool vis[N];
int n, m, d[N];
int idx, hd[N], nxt[M], edg[M];
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &e[i].first, &e[i].second);
        d[e[i].first]++, d[e[i].second]++;
    }
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].first, v = e[i].second;
        if (d[u] > d[v] || (d[u] == d[v] && u > v))
            swap(u, v);
        add(u, v);
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = hd[i]; ~j; j = nxt[j])
            vis[edg[j]] = true;
        for (int j = hd[i]; ~j; j = nxt[j])
            for (int k = hd[edg[j]]; ~k; k = nxt[k])
                res += vis[edg[k]];
        for (int j = hd[i]; ~j; j = nxt[j])
            vis[edg[j]] = false;
    }
    printf("%d", res);
    return 0;
}