三元环计数

原理

不常用的黑科技——「三元环」

模板题

XDOJ-1187-大红数星星

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
struct edge {
    int to, next;
};
edge e[N];
int idx, head[N], deg[N];
struct node {
    int u, v;
};
int n, m;
node a[N];
int mark[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        idx = 0;
        memset(head, -1, sizeof(head));
        memset(deg, 0, sizeof(deg));
        memset(mark, 0, sizeof(mark));

        cin >> n >> m;
        for (int i = 1, u, v; i <= m; ++ i) {
            cin >> u >> v;
            a[i] = { u, v };
            ++ deg[u], ++ deg[v];
        }

        for (int i = 1; i <= m; ++ i) { // 无向图 -> 有向无环图
            int u = a[i].u, v = a[i].v;
            if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
            add_edge(u, v);
        }
        int res = 0;
        for (int x = 1; x <= n; ++ x) {
            for (int i = head[x]; i != -1; i = e[i].next) {
                int y = e[i].to;
                mark[y] = x;
            }

            for (int i = head[x]; i != -1; i = e[i].next) {
                int y = e[i].to;
                for (int j = head[y]; j != -1; j = e[j].next) {
                    int z = e[j].to;
                    if (mark[z] == x) ++ res;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}