Skip to content

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;
}