10720.线图

题目分析

题目的核心是计算一个无向简单图 $G$ 的线图 $L(G)$ 中的边数。
所谓线图，就是将原图的边视为新图的结点，如果原图中两条边共用一个端点，那么它们对应的新结点之间就有一条边。
因此，线图中边的数量等价于原图中所有相邻边对的数量（即拥有公共端点的不同无序边对的数量）。

由于 $G$ 是简单图（无重边、无自环），任意两条边最多只会在一个端点处相邻，所以我们可以独立地处理每个结点：统计以该结点为一端的所有边，这些边两两之间都会在线图中产生一条边。

解题思路

对于原图中的一个结点 $v$，设它的度数为 $d(v)$，即有多少条边以 $v$ 为端点。
这 $d(v)$ 条边在 $L(G)$ 中对应 $d(v)$ 个结点，且任意两条这样的边都满足“有公共端点”的条件，因此对应的结点之间两两相连，形成一个完全图。在一个 $d(v)$ 个点的完全图中，边数为：

由于前文提到的“任意两条边最多共用一个端点”，不同结点的贡献不会重复计算同一对边。因此 $L(G)$ 的总边数就是所有结点贡献的完全图边数之和：

算法步骤

1. 读入 $n$ 和 $m$，并初始化度数数组 deg（长度为 $n+1$）。
2. 遍历 $m$ 条边，每读入一条边 $(u,v)$，将 deg[u] 和 deg[v] 分别加 $1$。
3. 遍历 $1$ 到 $n$，对于每个顶点 $i$，令 ans += deg[i] * (deg[i] - 1) / 2。
4. 输出 ans。

参考代码

cpp
复制
1#include <cstdio>
2using namespace std;
3
4const int N = 1e5 + 5;
5int n, m, deg[N];
6long long ans;
7
8int main() {
9    scanf("%d%d", &n, &m);
10    while (m--) {
11        int u, v;
12        scanf("%d%d", &u, &v);
13        deg[u]++;
14        deg[v]++;
15    }
16    for (int i = 1; i <= n; i++)
17        ans += 1ll * deg[i] * (deg[i] - 1) / 2;
18    printf("%lld\n", ans);
19    return 0;
20}

代码解释

• deg 数组统计每个结点的度数，下标从 $1$ 到 $n$。
• 读入每条边时，直接对两个端点的度数加一，不需要存储整张图。
• 使用 long long 类型存储答案 ans，因为当某个结点的度数很大时（例如接近 $n$），deg[i] * (deg[i] - 1) / 2 可能超出 int 范围。1ll * ... 确保了乘法在 long long 下进行。
• 最终输出 %lld 格式的 ans。

时间复杂度分析

• 读入 $m$ 条边并更新度数的复杂度为 $O(m)$。
• 求和需要遍历 $n$ 个结点，复杂度为 $O(n)$。
• 总时间复杂度为 $O(n + m)$，可以在 $n, m \le 10^5$ 的数据范围内快速运行。

空间复杂度为 $O(n)$（仅需存储度数数组）。

注意事项

1. 数据范围：题目未明确给出 $n, m$ 的上限，但从参考代码可以看出 $n$ 最多约 $10^5$，使用的 long long 可以避免 $m$ 很大时答案溢出。
2. 简单图保证不重不漏：由于图中无重边、无自环，两条边不可能在两个端点处都相邻，因此按结点分别累加 $C(d,2)$ 不会重复计算。
3. 整型运算：计算组合数时务必使用 long long 并注意运算顺序，deg[i] * (deg[i] - 1) / 2 在 deg[i] 为 int 时仍然会先进行 int 乘法（可能导致溢出），因此代码中使用 1ll * deg[i] * (deg[i] - 1) / 2 进行强制类型转换。