题解 | #统计个数#

数据结构

为了平衡空间与查询速度，针对 ：

• 邻接矩阵 (Adjacency Matrix)：使用二维布尔数组 adj[N][N]。
  • 优势：判断两点间是否有边的时间复杂度为 。这对于三角统计中的频繁查边操作至关重要。
  • 空间消耗： 是极其微小的内存开销。
• 度数数组 (Degree Array)：数组 degree[N]。
  • 用途：存储每个节点的度（连接的边数），用于快速计算“线”的数量。

核心算法

• 线 的统计 —— 组合数学法

  • 也就是以每个节点 为中心，从其所有邻居中任选 2 个点。
  • 若节点 的度数为 ，则以 为中心的线的数量为组合数 。
  • 总线数 。
  • 此方法避免了复杂的路径搜索，将复杂度从搜索路径降为简单的数值累加。

• 三角 的统计 —— 暴力枚举优化

  • 由于我们要统计的是无序的三元组 ，为了避免重复计数（例如统计了 就不能统计 ），我们人为规定节点序：。
  • 遍历所有满足 的组合，检查 adj[i][j]、adj[j][k] 和 adj[i][k] 是否同时为真。
  • 总三角数 。

结果计算

• 目标输出：分数 ，其中 ，。
• 最简分数处理：需要计算 和 的最大公约数 ，输出 。
• 边界处理：题目保证 ，若 ，输出 0/1。

代码实现

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

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
    vector<int> degree(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = graph[b][a] = 1;
        degree[a]++;
        degree[b]++;
    }

    ll lines = 0LL;
    ll triangles = 0LL;

    for (int i = 1; i <= n; i++) {
        ll v = degree[i];
        if (v > 0) {
            lines += v * (v - 1) / 2;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (graph[i][j] && graph[j][k] && graph[i][k]) {
                    triangles++;
                }
            }
        }
    }
    triangles *= 3LL;

    ll g = gcd(lines, triangles);
    ll p = triangles / g;
    ll q = lines / g;
    if (p == 0) {
        cout << "0/1\n";
    } else {
        cout << p << "/" << q << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        solve();
    }
}

复杂度分析

时间复杂度

1. 构建图与度数统计：
   • 读取 条边，填充邻接矩阵并更新度数数组。
   • 复杂度：。
2. 统计线：
   • 遍历 个节点计算组合数。
   • 复杂度：。
3. 统计三角：
   • 三层循环嵌套 。
   • 循环次数为 。
   • 复杂度：。
4. GCD 计算：
   • 对数级复杂度，相对于 可忽略不计。

总时间复杂度：。

空间复杂度

• 邻接矩阵：。
• 辅助数组：。
• 总空间复杂度：。符合内存限制。