题目描述
给定由 n 个结点与 m 条边构成的简单无向图 G，结点依次以 1,2,…,n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建：
-
初始时线图 L(G) 为空。
-
对于无向图 G 中的一条边，在线图 L(G) 中加入与之对应的一个结点。
-
对于无向图 G 中两条不同的边 (u1,v1),(u2,v2)，若存在 G 中的结点同时连接这两条边（即 u1,v1 之一与 u2,v2 之一相同），则在线图 L(G) 中加入一条无向边，连接 (u1,v1),(u2,v2) 在线图中对应的结点。
请你求出线图 L(G) 中所包含的无向边的数量。
输入格式
第一行，两个正整数 n,m，分别表示无向图 G 中的结点数和边数。
接下来 m 行，每行两个正整数 ui,vi，表示 G 中连接 ui,vi 的一条无向边。
输出格式
输出共一行，一个整数，表示线图 L(G) 中所包含的无向边的数量。
输入输出样例
输入 #1
5 4 1 2 2 3 3 1 4 5
输出 #1
3
输入 #2
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
输出 #2
30
说明/提示
【样例解释 #1】
【数据范围】
对于 60% 的测试点，保证 1≤n≤500,1≤m≤500。
对于所有测试点，保证 1≤n≤105,1≤m≤105。
【题目大意】给定一个简单无向图G（无自环和重边），要求构造它的线图L(G)，并计算L(G)中的边数。线图的构造规则：
原图G的每条边对应线图L(G)的一个顶点。
若原图G中两条边共享一个公共顶点，则在线图L(G)中对应的两个顶点之间连一条边。
【考纲知识点】
图的定义及遍历
【解题思路】
线图性质理解：线图L(G)的边数等于原图G中所有共享顶点的边对数。即对于原图G中的每个顶点v，计算其度数d(v)，然后贡献C(d(v),2)（即d(v)选2的组合数）到总边数中。
数学转化：总边数= Σ[C(d(v),2)]，其中d(v)是顶点v的度数。这可以简化为Σ[d(v)*(d(v)-1)/2]。
解题步骤：
1.先统计每个顶点的度数d(v)。
2.遍历所有顶点，累加每个顶点的C(d(v),2)。
【参考程序】
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, m, deg[N];
long long ans;
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
// 每条边会增加两个端点的度数
deg[u]++;
deg[v]++;
}
// 对每个节点，计算其度数对应的边组合数并累加
for (int i = 1; i <= n; i++)
ans += (long long)deg[i] * (deg[i] - 1) / 2;
printf("%lld\n", ans);
return 0;
}