图论 环计数问题

#include <bits/stdc++.h>

#define N 100010
using namespace std;

struct Edge {
    int to, ne;
} edges[N << 1];

int h[N], idx = 0;
int deg[N << 1];
bool st[N << 1];
int u[N << 1], v[N << 1];

void add(int a, int b) {
    idx++;
    edges[idx].to = b;
    edges[idx].ne = h[a];
    h[a] = idx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        deg[u[i]]++;
        deg[v[i]]++;
    }
    for (int i = 1; i <= m; i++) {
        if ((deg[u[i]] == deg[v[i]] && u[i] > v[i]) || deg[u[i]] > deg[v[i]]) swap(u[i], v[i]);
        add(u[i], v[i]);
    }
    int cnt = 0;
    for (int u = 1; u <= n; u++) {
        for (int i = h[u]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            st[j] = true;
        }
        for (int i = h[u]; ~i; i = edges[i].ne) {
            int v = edges[i].to;
            for (int j = h[v]; ~j; j = edges[j].ne) {
                int w = edges[j].to;
                if (st[w]) cnt++;
            }
        }
        for (int i = h[u]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            st[j] = false;
        }
    }
    cout << cnt << endl;
    return 0;
}