求线图 L(G) 的边数:按"共享顶点"分类计数,答案 = Σ C(deg(v), 2)。
给定由 n 个结点、m 条边构成的简单无向图 G,结点编号 1 ~ n。简单无向图意味着 G 中不含重边与自环。
G 的线图 L(G) 这样构造:
求 L(G) 中所包含的无向边的数量。
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 |
C(m, 2),m = 10⁵ 时约 5 × 10⁹,必然超时C(d, 2) = d(d − 1) ÷ 2边为 (1,2)、(2,3)、(3,1)、(4,5)。先数每个结点的度数。
| 结点 | 相邻的边 | 度数 deg(v) | 贡献 C(deg, 2) |
|---|---|---|---|
| 1 | (1,2)、(3,1) | 2 | 1 |
| 2 | (1,2)、(2,3) | 2 | 1 |
| 3 | (2,3)、(3,1) | 2 | 1 |
| 4 | (4,5) | 1 | 0 |
| 5 | (4,5) | 1 | 0 |
1 + 1 + 1 + 0 + 0 = 3 ✓
(1,2) 与 (2,3):共享结点 2 ✓
(2,3) 与 (3,1):共享结点 3 ✓
(3,1) 与 (1,2):共享结点 1 ✓
(4,5) 与其它任何边共享端点吗?没有 ✗
所以 L(G) 的边 = 3 条
✅ 与公式一致
全部边对 C(4,2) = 6 对
相邻的 3 对(上面列出的)
不相邻的 3 对:(1,2)-(4,5)、(2,3)-(4,5)、(3,1)-(4,5)
3 + 3 = 6 ✓ 分类完整
✅ 无遗漏
K₅ 中任意两个结点都有边,所以每个结点的度数都是 5 − 1 = 4。
5 个结点,每个度数 4
每个结点贡献 C(4, 2) = 6
总和 5 × 6 = 30
✅ 30
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) | 两个点度数为 1 | 0(线图只有 1 个孤立点) |
| 路径 1-2-3-4 | 度数 1, 2, 2, 1 | 1 + 1 = 2 |
| 星形(中心连 k 条边) | 中心度数 k | C(k, 2) = k(k−1)/2 |
| 三角形 K₃ | 度数全为 2 | 3 × 1 = 3 |
| 完全图 Kₙ | 度数全为 n−1 | n × C(n−1, 2) |
统计每个顶点的度数,把贡献 C(deg(v), 2) 累加起来
双重循环检查每两条边是否共享端点
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) | ❌ 超时 |
第一行输入 n m,随后 m 行每行一条边 u v。程序按顶点统计贡献,并列出每个非孤立点的贡献明细(m ≤ 2000 时还会用暴力枚举边对交叉验证)。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 当成遗漏。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 4 | 3 | 题面样例 1 |
5 10 | 30 | 题面样例 2(完全图 K₅) |
2 1 | 0 | 只有一条边,线图无边 |
6 3 | 3 | 星形:中心度数 3 → C(3,2) = 3 |
4 3 | 2 | 路径:度数 1,2,2,1 → 1 + 1 = 2 |
3 3 | 3 | 三角形:三个点度数都是 2 |
5 4 | 4 | 度数 3 与度数 2:C(3,2) + C(2,2) = 4 |
d × (d − 1) ÷ 2 吗?③ 复杂度 O(n + m) 吗?④ 读边时两端度数都加了吗?只需要一个度数数组 deg((n + 1) 个 int ≈ 400 KB),连邻接表都不用建。
✅ 线性时间,稳过。相比枚举边对的约 5 × 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 意识 | 先估答案上界再选类型 | 所有组合计数题的第一步 |
deg(u) + deg(v) − 2(两端各要减掉它自己)。你还可以用它交叉验证本题答案:线图边数 = 线图所有点度数之和 ÷ 2。)