这是我写的第4个正式题解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【A75421】[GESP202506 七级] 线图
题目链接
点这里
题目大意
有一张 nnn 个结点，mmm 条边的简单无向图
这题不太好理解（因为形式化概念太多）
简单来讲，这道题需要我们构建一个线图（L(G)L(G)L(G)）
线图的构造方式：
* 对于每条边，先加入到线图中当做一个点
* 对于两个点，如果这两个点分别对应的边有任何起始或终点节点重合，则将这两个节点间插入一条无向边
最终求线图中有多少条无向边
解题思路
1. 算法选择
数组记录度+组合数的计算
2. 核心思路
将每个点的度数记录（维护一个deg数组）
对于每个节点，求 Cdegi2C_{deg_i} ^ 2Cdegi 2 并累加求和直接得到最终答案
> Q：为什么可以使用Cdegi2C_{deg_i} ^ 2Cdegi 2 累加求和得到答案？
> A：我们要算的是：原图中每一对 “共享同一个节点的边”，会在线图里连一条边。
> 从 degideg_idegi 条边里挑出 2 条，一共有多少种挑法？这就是组合数Cdegi2C_{deg_i} ^ 2Cdegi 2
> 计算公式：d×(d−1)2\dfrac{d \times (d - 1)}{2}2d×(d−1)
3. 复杂度分析
* 时间复杂度：O(n+m)O(n+m)O(n+m)
* 空间复杂度：O(n)O(n)O(n)
易错点/坑点
十年OI一场空，不开LONGLONG见祖宗！
对于这道题 105×(105−1)÷2≈5×10910^5 \times (10^5-1) \div 2 \approx 5 \times 10^9105×(105−1)÷2≈5×109，超过了int限制
AC 代码
