G7013 [GESP202506 七级] 线图 题解

知识点：图的度数、组合计数、整数范围。

解题思路

统计原图每个点的度数d，累加d(d-1)/2，即为线图边数。

为什么正确

线图中两条原边相邻当且仅当共享原顶点，选取该顶点任意两条关联边恰产生一条线图边；简单图中不会重复。

易错点

无需显式建立可能很大的线图；组合数与总和用long long。

复杂度

时间O(n+m)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<long long>d(n+1);
    while(m--) {
        int u,v;
        cin>>u>>v;
        d[u]++;
        d[v]++;
    }
    long long ans=0;
    for(auto x:d)ans+=x*(x-1)/2;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。