GESP 题解库 / 7 级题解 / [GESP202506 七级] 线图 · 第 8 / 24 题
GESP202506 七级 · P13017 · 中等

线图的边数

求线图 L(G) 的边数:按"共享顶点"分类计数,答案 = Σ C(deg(v), 2)。

📊
n, m ≤ 10⁵
图规模
🔢
long long
答案可达 ~5 × 10⁹
⚡
O(n + m)
时间复杂度
🎯
度数组合计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定由 n 个结点、m 条边构成的简单无向图 G,结点编号 1 ~ n。简单无向图意味着 G 中不含重边与自环。

G 的线图 L(G) 这样构造:

求 L(G) 中所包含的无向边的数量。

💡
人话翻译:线图把"边"当"点"用——G 的边数 m 就是 L(G) 的点数;L(G) 的一条边 ⟺ G 中"共享端点的一对边"。
所以题目只要求:G 里有多少对相邻(共享端点)的边。
怎么不重不漏地数?按"它们共享的那个顶点 v"来分类:顶点 v 上挂着 deg(v) 条边,两两配对就是 C(deg(v), 2) 对,把所有顶点的贡献加起来即可。

🔍 关键词提取

线图度数组合计数交换求和long long

已知条件

项目说明
输入第一行 n, m;随后 m 行每行一条无向边 uᵢ vᵢ
输出L(G) 的边数
数据范围1 ≤ n, m ≤ 10⁵
部分分60%:n, m ≤ 500
图的性质简单无向图:无重边、无自环
L(G) 的点数恰好等于 m(G 的每条边对应一个点)
答案规模最大约 C(10⁵, 2) ≈ 5 × 10⁹,必须 long long

需要解决的问题

02
思维导图
整理解题思路的全貌
📐 线图边数 = Σ C(deg(v), 2)
🔁 等价转化
L(G) 的点 ↔ G 的边(共 m 个)
L(G) 的边 ↔ G 中共享端点的边对
问题变成:统计"相邻边对"的个数
每对相邻边共享 1 个顶点
🧮 分类计数
以"共享的那个顶点"为分类依据
顶点 v 上有 deg(v) 条边
两两配对 → C(deg(v), 2)
对所有顶点求和即不重不漏
🛡️ 为什么不重不漏
若两条边同时共享 u 和 v
则它们的端点集合都是 {u, v}
简单图无重边 → 这只能是同一条边
与"两条不同边"矛盾,故每个顶点最多数一次
⚠️ 易错点
用 int 存答案(可达 5 × 10⁹)
把 C(d, 2) 写成 d × d
按两个端点各数一遍导致翻倍
n = 1 或 m = 1 的边界要返回 0
03
样例手算推导
样例的完整推演

🧮 样例 1:n = 5, m = 4,答案 3

边为 (1,2)、(2,3)、(3,1)、(4,5)。先数每个结点的度数。

结点相邻的边度数 deg(v)贡献 C(deg, 2)
1(1,2)、(3,1)21
2(1,2)、(2,3)21
3(2,3)、(3,1)21
4(4,5)10
5(4,5)10

1 + 1 + 1 + 0 + 0 = 3 ✓

1
把 3 对边具体找出来

(1,2) 与 (2,3):共享结点 2 ✓

(2,3) 与 (3,1):共享结点 3 ✓

(3,1) 与 (1,2):共享结点 1 ✓

(4,5) 与其它任何边共享端点吗?没有 ✗

所以 L(G) 的边 = 3 条

✅ 与公式一致

2
用"总边对"反向核对

全部边对 C(4,2) = 6 对

相邻的 3 对(上面列出的)

不相邻的 3 对:(1,2)-(4,5)、(2,3)-(4,5)、(3,1)-(4,5)

3 + 3 = 6 ✓ 分类完整

✅ 无遗漏

🔑
注意顶点 1、2、3 各自贡献 1:三角形 (1,2)、(2,3)、(3,1) 的三条边两两相邻,所以线图里这 3 个点构成一个三角形,贡献 3 条边。
而这三对边分别在顶点 1、2、3 处被数到:(1,2)-(3,1) 在顶点 1,(1,2)-(2,3) 在顶点 2,(2,3)-(3,1) 在顶点 3——每个顶点正好负责一对,这就是"不重不漏"的直观体现。

🧮 样例 2:n = 5, m = 10(完全图 K₅),答案 30

K₅ 中任意两个结点都有边,所以每个结点的度数都是 5 − 1 = 4。

1
直接套公式

5 个结点,每个度数 4

每个结点贡献 C(4, 2) = 6

总和 5 × 6 = 30

✅ 30

2
用补集法交叉验证

10 条边的全部边对:C(10, 2) = 45 对

"不相邻"的边对 = 4 个不同顶点配成两对边

选 4 个顶点:C(5, 4) = 5 种;再把这 4 点两两配成 2 条边:3 种

所以不相邻边对 = 5 × 3 = 15 对

相邻边对 = 45 − 15 = 30 ✓

✅ 与公式一致

📊 几种特殊图的对照

图 G度数特点L(G) 的边数
一条边 (m = 1)两个点度数为 10(线图只有 1 个孤立点)
路径 1-2-3-4度数 1, 2, 2, 11 + 1 = 2
星形(中心连 k 条边)中心度数 kC(k, 2) = k(k−1)/2
三角形 K₃度数全为 23 × 1 = 3
完全图 Kₙ度数全为 n−1n × C(n−1, 2)
⚠️
这组对照说明:答案完全由度数序列决定,与"边具体连到谁"无关——两条不同的图只要有相同的度数序列,它们的线图边数就相同。
这正是"按顶点分类计数"这类套路的特点:把结构信息浓缩成一个可加的量(这里是度数),再把"总数"写成它在各个顶点上的求和。
04
解法对比
度数公式 vs 暴力枚举边对

⚔️ 解法对比

🟢 按顶点分类计数(推荐) 推荐

统计每个顶点的度数,把贡献 C(deg(v), 2) 累加起来

  • 时间 O(n + m)
  • 空间 O(n):一个度数数组
  • 代码约 15 行
  • 不重不漏,且天然支持 m = 10⁵
💡
为什么这样数不会重复:一对相邻边被"数"的条件是"它们共享那个顶点",而简单图里两条不同边不可能共享两个端点(否则就是重边),所以每对相邻边只会在唯一的一个顶点处被配对一次。

🟠 暴力枚举边对

双重循环检查每两条边是否共享端点

  • 时间 O(m²) ≈ 5 × 10⁹
  • 只能拿 60%(m ≤ 500)
  • 代码虽短,但大数据必超时
  • 直观,适合用来对拍
⚠️
m = 500 时 C(500, 2) ≈ 1.2 × 10⁵,轻松通过;但 m = 10⁵ 时约 5 × 10⁹ 次判断,哪怕每次只要一个 if,也远远超过 1 秒的极限。

📈 性能对比

方案复杂度代码量
按顶点分类计数O(n + m)约 15 行
暴力枚举边对O(m²) ≈ 5 × 10⁹❌ 超时
用 set 去重相邻边对O(m² log m)❌ 超时
05
算法流程图
两遍扫描:先数度数,再累加组合数
开始读入 n, m;度数数组 deg[1..n] 清零逐条读边 (u, v):deg[u]++, deg[v]++m 条边都读完了吗?ans = 0(long long 类型)枚举顶点 v:ans += deg[v] × (deg[v] − 1) ÷ 2n 个顶点都统计完了吗?输出 ans继续下一个顶点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📐 线图 L(G) 的边数

第一行输入 n m,随后 m 行每行一条边 u v。程序按顶点统计贡献,并列出每个非孤立点的贡献明细(m ≤ 2000 时还会用暴力枚举边对交叉验证)。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(度数组合计数)

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

int deg[100005];          // deg[v] = 结点 v 的度数

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        deg[u]++;         // 一条边给两个端点的度数各加 1
        deg[v]++;
    }

    long long ans = 0;    // 答案可达约 5 × 10⁹,必须 long long
    for (int v = 1; v <= n; v++) {
        long long d = deg[v];
        // 顶点 v 上的 d 条边两两配对,贡献 C(d, 2) 对"相邻边"
        ans += d * (d - 1) / 2;
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么不必去重、不必特判?有人担心"一对边同时共享两个端点会被数两次",但在简单图里这不可能发生:若两条边共享 u 又共享 v,那它们都是 (u,v),是同一条边。
所以"按顶点分类"天然不重不漏——这也是题目特意强调"不含重边与自环"的原因。如果图里有重边,这个结论就不成立了。

📖 关键几行怎么看

代码作用为什么这样写
deg[u]++; deg[v]++;统计度数每条边读入时 O(1) 更新两端
for (v = 1; v <= n; v++)遍历所有顶点孤立点 deg = 0,贡献 0,无须特判
ans += d * (d − 1) / 2;核心公式顶点 v 上"边对"的个数 = C(d, 2)
long long ans类型最大约 5 × 10⁹,超出 int 范围
⚠️
四个坑:① 用 int 存答案(把 10⁵ 条边全挂在一个点上时答案约 5 × 10⁹,会溢出成负数);② 把 C(d, 2) 写成 d × d(多算了 d 对);③ 担心重复计数而画蛇添足地去重(简单图不需要);④ 只统计"有边的点"却把孤立点的 0 当成遗漏。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 4
1 2
2 3
3 1
4 5
3题面样例 1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
30题面样例 2(完全图 K₅)
2 1
1 2
0只有一条边,线图无边
6 3
3 1
3 2
3 4
3星形:中心度数 3 → C(3,2) = 3
4 3
1 2
2 3
3 4
2路径:度数 1,2,2,1 → 1 + 1 = 2
3 3
1 2
1 3
2 3
3三角形:三个点度数都是 2
5 4
1 2
1 3
4 5
4 1
4度数 3 与度数 2:C(3,2) + C(2,2) = 4
✅
自查清单:① 用 long long 吗?② 公式是 d × (d − 1) ÷ 2 吗?③ 复杂度 O(n + m) 吗?④ 读边时两端度数都加了吗?

🚨 易错点清单

⚠️
int 溢出:边数 m ≈ 10⁵ 且所有边共用一个端点(星形)时,答案约 5 × 10⁹ > 2³¹ − 1。
⚠️
C(d, 2) 写成 d × d:公式是 d(d − 1) ÷ 2,别漏了"减 1 ÷ 2"。
⚠️
重复计数:简单图中两条不同边最多共享一个端点,按顶点分类天然不重不漏,不要额外去重。
⚠️
孤立点:deg = 0 的点贡献 0,遍历时不必跳过也不会算错。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + m)
空间复杂度
O(n)
n, m 最大
10⁵
答案上界
C(10⁵, 2) ≈ 5 × 10⁹

时间怎么算的?

空间都用在哪?

只需要一个度数数组 deg((n + 1) 个 int ≈ 400 KB),连邻接表都不用建。

✅ 线性时间,稳过。相比枚举边对的约 5 × 10⁹ 次判断,把"数边对"改成"数每个顶点的组合数"直接快了几个数量级——这就是交换求和顺序的威力。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 线图边数 = 对所有顶点 v 求和 C(deg(v), 2)
long long ans = 0;
for (int v = 1; v <= n; v++) {
    long long d = deg[v];
    ans += d * (d - 1) / 2;      // 先乘后除,避免中间精度问题
}

// 【等价写法】利用 Σ deg(v) = 2m
//   Σ C(deg,2) = (Σ deg(v)² − Σ deg(v)) / 2 = (Σ deg(v)² − 2m) / 2

// 【线图里点的度数】G 的边 (u,v) 对应 L(G) 的点,
//   它的度数是 deg(u) + deg(v) − 2
//   可用它交叉验证:线图边数 = (线图所有点度数之和) / 2

// 【通用套路】"统计满足某条件的元素对个数"
//   ① 找一个"分类依据"(本题是共享顶点)
//   ② 让每一类内部的元素两两配对 → C(cnt, 2)
//   ③ 各类求和,检查是否不重不漏

// 【同类计数】Σ C(cnt, 2) 也出现在"等价消除"(前缀掩码计数)等题里

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
交换求和顺序把"数边对"变成"数每个顶点的组合数"图论计数、二维网格计数、配对统计
组合数 C(d, 2)度 d 的点贡献 d(d − 1) ÷ 2握手问题、同色对数、团与线图计数
求和恒等式Σ deg(v) = 2m度数换边数、线图点数/边数关系
long long 意识先估答案上界再选类型所有组合计数题的第一步
🌟
思考题:L(G) 里每个点的度数是多少?(提示:G 的边 (u,v) 在 L(G) 中与"所有和它共享 u 的边"以及"共享 v 的边"相邻,所以度数是 deg(u) + deg(v) − 2(两端各要减掉它自己)。你还可以用它交叉验证本题答案:线图边数 = 线图所有点度数之和 ÷ 2。)