14209: 【原4209】quaternary

题目

题目描述

author: Chen Yuxuan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4209

Description

轩轩喜欢数数，他希望你帮他数数：一个无重边无自环的无向图 \(G(V, E)\) 中四元环的个数。

四元环的定义：

有序 四元组\((x, y, z, r)\)

其中 \(x,y,z,r \in V，(x, y), (y, z), (z, r), (r, x) \in E\)

(当然，\(x, y, z, r\) 还需要是两两不同的)

Input Format

第一行两个整数 \(n\) 和 \(m\)，表示无向图的点数和边数，\(V = {1, 2, 3\cdots, n}, |E| = m\)

接下来 \(m\) 行，每行两个整数 \(x_i\) 和 \(y_i\)，表示 \((x_i, y_i) \in E\)

n m
x_1 y_1
x_2 y_2
...
x_m y_m

Output Format

一行，一个整数，表示给定的图 \(G\) 中四元环的个数。

Sample Input

4 4
1 2
2 3
3 4
4 1

Sample Output

8

Limits

\(1 \leq n \leq 10^5, 0 \leq m \leq 2*10^5, 1\leq x_i, y_i \leq n\,(x_i, y_i\in V)​\)，图 \(G​\) 无重边无自环。

| case | n | m | else | | ------ | ------ | ------ | ------ | | 0 | 10 | 30 | | | 1 | 100 | 500 | | | 2 | 1000 | 5000 | | | 3 | 2000 | 10000 | | | 4 | 10000 | 10^5 | | | 5 | 20000 | 10^5 | | | 6 | 40000 | 10^5 | | | 7 | 10^5 | 10^5 | G为连通图 | | 8 | 10^5 | 210^5 | | | 9 | 10^5 | 210^5 | |

Hint

计算时间复杂度会让你更有信心。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/tutorials_and_notes/blob/master/algo_notes/cycle_counting.md
*/ 
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int du[100005] = {0}, rk[100005];
int to[200005], nxt[200005], at[100005] = {0}, cnt = 0;
int to2[400005], nxt2[400005], at2[100005] = {0}, cnt2 = 0;
int pcnt[100005] = {0};
pair<int, int> pp[100005];
void init(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i){
        int u = read(), v = read();
        ++du[u], ++du[v];
        to2[++cnt2] = v, nxt2[cnt2] = at2[u], at2[u] = cnt2;
        to2[++cnt2] = u, nxt2[cnt2] = at2[v], at2[v] = cnt2;
    }
    for (int i = 1; i <= n; ++i)
        pp[i].first = -du[i], pp[i].second = -i;        // 降序
    sort(pp + 1, pp + n + 1);
    for (int i = 1; i <= n; ++i)
        rk[-pp[i].second] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = at2[i]; j; j = nxt2[j])
            if (rk[i] < rk[to2[j]])
                to[++cnt] = to2[j], nxt[cnt] = at[i], at[i] = cnt;
}
void solve(){
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
        int id = -pp[i].second;
        int v, vv;
        for (int j = at[id]; j; j = nxt[j]){
            v = to[j];
            for (int k = at2[v]; k; k = nxt2[k])
                if (i < rk[to2[k]])
                    ans += pcnt[to2[k]]++;
        }
        for (int j = at[id]; j; j = nxt[j]){
            v = to[j];
            for (int k = at2[v]; k; k = nxt2[k])
                pcnt[to2[k]] = 0;
        }
    }
    printf("%lld\n", 8ll * ans);
}
int main(){
    init();
    solve();
    return 0;
}