题解:P13017 [GESP202506 七级] 线图
首先明白定义: 线图 L(G)L(G)L(G) 的顶点对应原图 GGG 的边,当且仅当原图中的两条边有公共顶点时,对应的线图顶点之间有一条边。
不难想到,对于原图中的每个顶点 vvv,其度数 d(v)d(v)d(v) 对应的边集可以形成 (d(v)2)\binom{d(v)}{2}(2d(v)) 对相邻边。每对相邻边在线图中会产生一条边。
用公式表示就是这样的(设 G=(V,E)G = (V,E)G=(V,E)):
∣EL(G)∣=∑v∈V(d(v)2)=∑v∈Vd(v)×(d(v)−1)2|E_{L(G)}| = \sum\limits_{v \in V} \binom{d(v)}{2} = \sum\limits_{v \in V} \frac{d(v) \times (d(v) - 1)}{2}∣EL(G)∣=v∈V∑(2d(v))=v∈V∑2d(v)×(d(v)−1)
Code:
#include <bits/stdc++.h>
#define int long long // 开long long!
using namespace std;
signed main() {int n, m;cin >> n >> m;vector<int> d(n + 1, 0);// 统计每个顶点的度数for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;d[u]++, d[v]++;}// 计算所有顶点的度数组合数之和int ans = 0;for (int i = 1; i <= n; ++i) {ans += d[i] * (d[i] - 1) / 2;}cout << ans << endl;return 0;
}