首先明白定義: 線圖 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;
}