题解

之前懒得实名认证因此很久没有发帖，当然这不重要。

思路

题目大意：将原图 $G$ 浓缩的一条无向边浓缩成线图 $G$ 一个节点代表，如果两条无向边共顶点的话就将线图 $G$ 的对应点连起来。

因此，遍历每个节点，再遍历其作为一个顶点的边，共 当前遍历的点 的边 的 数量 就是存储点 i 出边的数组 a[i] 的元素个数。a[i].size()（下文简化为 x）只是共一个顶点的边的数量，由题意得这些边两两配对即成为线图 $G$ 中的一条边，简化为在 x 中选2个的数量，为选择数：

$$C^2_x={\frac{x!}{2!·(x-2)!}=\frac{x·(x-1)}{2}}$$

得到公式，对于每个点 i 计算即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;

ll n,m,res;
vector<ll> a[N];

int main(){
	ios::sync_with_stdio(0);cin.tie(nullptr);

	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll x,y;cin>>x>>y;
		a[x].push_back(y);a[y].push_back(x);
	}

	for(ll i=1;i<=n;i++){
		res+=a[i].size()*(a[i].size()-1)/2;
	}

	cout<<res;

	return 0;
}