BanG Dream! It's MyGO!!!!!

onlyblues / 2024-08-23 / 原文

BanG Dream! It's MyGO!!!!!

题目描述

在“BanG Dream! It's MyGO!!!”的世界里，各个乐团的演出和排练场地像星星一样被连接在一起，形成了一张美丽的网络图。每个乐团都有自己独特的演出场地和练习室，这些地点通过各种路径互相连接，组成了一张复杂的图谱。

koala 作为一名热爱音乐的乐团忠实粉丝，突然有了一个灵感。他想为最喜欢的乐团设计一个独特的徽章，这个徽章需要从网络图中找出一些特别的图案来代表乐团，比如选三条边连接到一起，具体来说，他对以下三种图案感兴趣：

三角形：由三条边构成的连通子图，这是一种经典的图案。

三芒星：四个点形成的图案，一个点连向其他三个点。

闪电折线：一种特别的折线，由四个点按顺序连接，即一条链。

koala 想知道有多少种情况满足，你能帮帮他吗？

输入描述:

第一行包合两个整数 $n,m$ $(1 \leq n \leq 10^5, 1 \leq m \leq 2 \cdot 10^5)$，依次表示无向图的点数和边数；接下来 $m$ 行，每行两个整數 $u,v$ $(1 \leq u,v \leq n)$，表示一条边 $(u,v)$ 题目保证无重边、自环。

输出描述:

输出包含一个整数，表示你的答案。

示例1

输入

输出

说明

满足条件的导出子图的边集分别为：

(1,2),(1,3),(2,3)
(1,2),(2,3),(2,4)
(1,3),(2,3),(3,5)
(1,2),(1,3),(2,4)
(1,2),(1,3),(3,5)
(2,4),(2,3),(3,5)
(1,3),(2,3),(2,4)
(1,2),(2,3),(3,5)

备注:

给定一个无向图，你需要给出三条边的导出子图是连通的情况数量。

解题思路

先考虑简单的三芒星，枚举每个节点 $u$，那么以 $u$ 为中心的三芒星的数量就是 $C_{d_u}^{3}$，其中 $d_u$ 指 $u$ 的度数。

再考虑闪电折线，我们可以枚举中间的边 $(u, v)$，那么以边 $(u,v)$ 为中心的折线数量就是 $(d_u - 1) \cdot (d_v - 1)$。需要注意的是该统计方法会顺便把每个三角形都统计了 $3$ 次。

最后是三角形，就是统计图中三元组的数量，可以参考无向图三元环计数。

根号分治做法的 AC 代码如下，时间复杂度为 $O\left(\frac{nm}{w}\right)$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5, M = 3000;

int x[N], y[N];
vector<int> g[N];
bool vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    LL ret = 0, s = 0;
    map<int, bitset<N>> mp;
    for (int i = 1; i <= n; i++) {
        int s = g[i].size();
        if (s >= 3) ret += s * (s - 1ll) * (s - 2) / 6;
        if (s > M) {
            for (auto &j : g[i]) {
                mp[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        ret += (g[x[i]].size() - 1ll) * (g[y[i]].size() - 1);
        if (g[x[i]].size() > g[y[i]].size()) swap(x[i], y[i]);
        if (g[x[i]].size() <= M) {
            if (g[y[i]].size() <= M) {
                for (auto &v : g[y[i]]) {
                    vis[v] = true;
                }
                for (auto &v : g[x[i]]) {
                    if (vis[v]) s++;
                }
                for (auto &v : g[y[i]]) {
                    vis[v] = false;
                }
            }
            else {
                auto &p = mp[y[i]];
                for (auto &v : g[x[i]]) {
                    if (p[v]) s++;
                }
            }
        }
        else {
            s += (mp[x[i]] & mp[y[i]]).count();
        }
    }
    ret -= s / 3 * 2;
    cout << ret;
    
    return 0;
}

建 DAG 做法的 AC 代码如下，时间复杂度为 $O(m \sqrt{m})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5, M = 250;

int x[N], y[N];
int deg[N];
vector<int> g[N];
bool vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        deg[x[i]]++, deg[y[i]]++;
    }
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        int s = deg[i];
        if (s >= 3) ret += s * (s - 1ll) * (s - 2) / 6;
    }
    for (int i = 1; i <= m; i++) {
        ret += (deg[x[i]] - 1ll) * (deg[y[i]] - 1);
        if (deg[x[i]] < deg[y[i]] || deg[x[i]] == deg[y[i]] && x[i] < y[i]) g[x[i]].push_back(y[i]);
        else g[y[i]].push_back(x[i]);
    }
    LL s = 0;
    for (int i = 1; i <= n; i++) {
        for (auto &j : g[i]) {
            vis[j] = true;
        }
        for (auto &j : g[i]) {
            for (auto &k : g[j]) {
                if (vis[k]) s++;
            }
        }
        for (auto &j : g[i]) {
            vis[j] = false;
        }
    }
    ret -= s * 2;
    cout << ret;
    
    return 0;
}