Counting Stars hdu

(idea)

假设每条边包含在(t)个三元环中，那么这条边的贡献就是$t * (t - 1) / 2 $。将点分为两类 ：

• 度数(deg le sqrt(m))的点归为第一类点，然后枚举点数，(O(msqrt(m)))。
• 度数(deg > sqrt(m))的点归为第二类点，然后枚举边数，(O(msqrt(m)))。

因为度数超过(sqrt(m))的点至多有(sqrt(m))级别个，比如完全图(m = frac{n*(n - 1)}{2})。其实复杂度我也没分析得很清楚 orz

(code)

需要快速判读两点之间是否连有一条边。就哈希一条边，加到set里面。

const int N = 100005;

int n, m;
int deg[N], pa[N];

bool use[N];

set<LL> s;
vector<int> G[N];

int main()
{
    while(scanf("%d %d", &n, &m) != EOF) {
        mem(pa, 0);
        mem(deg, 0);
        mem(use, 0);

        s.clear();
        Rep(i, 1, n) G[i].clear();

        Rep(i, 1, m) {
            int u, v;
            sc(u), sc(v);
            deg[u]++;
            deg[v]++;

            G[u].pb(v);
            G[v].pb(u);

            s.insert(1ll * u * n + v);
            s.insert(1ll * v * n + u);
        }

        int limit = sqrt(1.0 * m);

        LL ans = 0;
        Rep(i, 1, n) {
            use[i] = 1;
            for (auto v : G[i]) pa[v] = i;
            for (auto v : G[i]) if (!use[v]) {
                LL t = 0;
                if (deg[v] <= limit) {
                    for (auto vv : G[v]) if (pa[vv] == i) t++;
                }
                else {
                    for (auto vv : G[i]) if (s.find(1ll * vv * n + v) != s.end()) t++;
                }
                ans += (t * (t - 1) / 2);
            }
        }

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