HDU 6184 Counting Stars

一个三元环计数问题……
当然是转化出来的……

一开始没想到去计数三元环的思路，而是直接搜……
然后发现题目理解错了……

又发现这特么不就跟三元环数量有关么？？
巧的是薛昊之前问过我三元环计数，我还特意去看了几眼。不然真的可能卡不出来。

题意：
给你一张无向图，让你计数这样的子图。
V=(A,B,C,D) ， E=(AB,BC,CD,DA,AC)

思路：
一开始我以为必须是矩形，然后发现同一点的不同三元环都满足条件。
所以我只要找到这个点的所有三元环数量，任意挑出两个即可。记得去重

个人三元环计数方法如下：
首先枚举每一条遍，再判断两个端点，确定度数较少的点，从这个点进行扩展一条边，再判断这条遍的另一端是否有边与第一条边的另一端点相连。

其中有很多细节值得优化，比如说对于( sqrt(m) )为分界进行不同的判定。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;

vector<int> G[maxn];
int link[maxn];
bool vis[maxn];

set<ll> key;
int deg[maxn];

int main()
{
    int n, m, u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        key.clear();
        for (int i = 1; i <= n; i++) {
            G[i].clear();
            link[i]=vis[i] = false;
            deg[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            key.insert((ll)u * n + v);
            key.insert((ll)v * n + u);
            deg[u]++, deg[v]++;
        }
        int limit = sqrt(1.0 * m);
        ll ans = 0;
        for (int u = 1; u <= n; u++) {
            vis[u] = true;
            int sz = G[u].size();
            for (int i = 0; i < sz; i++)
                link[G[u][i]] = u;
            for (int i = 0; i < sz; i++) {
                int v = G[u][i];
                if (vis[v])
                    continue;
                ll sum = 0;
                if (deg[v] <= limit) {
                    int vz = G[v].size();
                    for (int j = 0; j < vz; j++) {
                        int k = G[v][j];
                        if (link[k] == u)
                            sum++;
                    }
                } else {
                    for (int j = 0; j < sz; j++) {
                        ll k = G[u][j];
                        ll val = k * n + v;
                        if (key.find(val) != key.end())
                            sum++;
                    }
                }
                ans += sum * (sum - 1) / 2;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}