这是我写的第4个正式题解

---

【A75421】[GESP202506 七级] 线图

题目链接

点这里

题目大意

有一张 $n$ 个结点，$m$ 条边的简单无向图
这题不太好理解（因为形式化概念太多）
简单来讲，这道题需要我们构建一个线图（$L(G)$）
线图的构造方式：

• 对于每条边，先加入到线图中当做一个点
• 对于两个点，如果这两个点分别对应的边有任何起始或终点节点重合，则将这两个节点间插入一条无向边

最终求线图中有多少条无向边

解题思路

1. 算法选择

数组记录度+组合数的计算

2. 核心思路

将每个点的度数记录（维护一个deg数组）
对于每个节点，求 $C_{deg_i} ^ 2$ 并累加求和直接得到最终答案

Q：为什么可以使用$C_{deg_i} ^ 2$累加求和得到答案？

A：我们要算的是：原图中每一对 “共享同一个节点的边”，会在线图里连一条边。
从 $deg_i$ 条边里挑出 2 条，一共有多少种挑法？这就是组合数$C_{deg_i} ^ 2$​
计算公式：$\dfrac{d \times (d - 1)}{2}$

3. 复杂度分析

• 时间复杂度：$O(n+m)$
• 空间复杂度：$O(n)$

易错点/坑点

十年OI一场空，不开longlong见祖宗！

对于这道题 $10^5 \times (10^5-1) \div 2 \approx 5 \times 10^9$，超过了int限制

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
// 啥也不说了好吧，十年oi一场空，不开longlong见祖宗

int n, m;
const int N = 1e5 + 10;
int deg[N];
// 初始化

signed main(){

    cin >> n >> m;
    for (int i = 1;i <= m;i++){
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    // 输入+记录度数
    int cnt = 0;
    for (int i = 1;i <= n;i++){
        cnt += deg[i] * (deg[i] - 1) / 2;
        // 套用组合数数学公式直接累加求和
    }
    cout << cnt;
    // 输出答案
    
    return 0;
}