桂林市网站建设_网站建设公司_H5网站_seo优化

2025年6月GESP真题及题解(C++七级): 线图

题目描述

给定由n nn个结点与m mm条边构成的简单无向图G GG，结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号。简单无向图意味着G GG中不包含重边与自环。G GG的线图L ( G ) L(G)L(G)通过以下方式构建：

• 初始时线图L ( G ) L(G)L(G)为空。

• 对于无向图G GG中的一条边，在线图L ( G ) L(G)L(G)中加入与之对应的一个结点。

• 对于无向图G GG中两条不同的边( u 1 , v 1 ) , ( u 2 , v 2 ) (u_1,v_1),(u_2,v_2)(u1​,v1​),(u2​,v2​)，若存在G GG中的结点同时连接这两条边（即u 1 , v 1 u_1,v_1u1​,v1​之一与u 2 , v 2 u_2,v_2u2​,v2​之一相同），则在线图L ( G ) L(G)L(G)中加入一条无向边，连接( u 1 , v 1 ) , ( u 2 , v 2 ) (u_1,v_1),(u_2,v_2)(u1​,v1​),(u2​,v2​)在线图中对应的结点。

请你求出线图L ( G ) L(G)L(G)中所包含的无向边的数量。

输入格式

第一行，两个正整数n , m n,mn,m，分别表示无向图G GG中的结点数和边数。

接下来m mm行，每行两个正整数u i , v i u_i,v_iui​,vi​，表示G GG中连接u i , v i u_i,v_iui​,vi​的一条无向边。

输出格式

输出共一行，一个整数，表示线图L ( G ) L(G)L(G)中所包含的无向边的数量。

输入输出样例 #1

输入 #1

5 4 1 2 2 3 3 1 4 5

输出 #1

3

输入输出样例 #2

输入 #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 % 60\%60%的测试点，保证1 ≤ n ≤ 500 1 \le n \le 5001≤n≤500，1 ≤ m ≤ 500 1 \le m \le 5001≤m≤500。

对于所有测试点，保证1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105，1 ≤ m ≤ 10 5 1 \le m \le 10^51≤m≤105。

思路分析

线图 L(G) 的边数等于原图 (G) 中所有共享一个公共顶点的边对数量。对于每个顶点 v，设其度数为 deg(v)，那么以 v为公共顶点的边对数为( d e g ( v ) 2 ) = d e g ( v ) × ( d e g ( v ) − 1 ) 2 \binom{deg(v)}{2} = \frac{deg(v) \times (deg(v)-1)}{2}(2deg(v)​)=2deg(v)×(deg(v)−1)​。因此，线图的边数即为所有顶点对应的边对数之和。

由于原图是简单无向图，不存在重边，所以每条线图的边只被一个公共顶点唯一确定，不会重复计数。

算法步骤：

1. 读入顶点数 n和边数 m。
2. 初始化度数数组deg[]，长度为n+1，所有元素置 0。
3. 对于每条边 (u, v)，将deg[u]和deg[v]各加 1。
4. 遍历所有顶点1 ∼ n 1 \sim n1∼n，累加每个顶点的b i n o m d e g [ i ] 2 binom{deg[i]}{2}binomdeg[i]2。
5. 输出结果，注意使用long long类型存储结果。

时间复杂度：

O(n + m)，满足题目数据范围要求。

空间复杂度：

O(n)，用于存储度数数组。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100005;intdeg[MAXN];// 存储每个顶点的度数intmain(){intn,m;scanf("%d%d",&n,&m);// 初始化度数数组for(inti=1;i<=n;i++)deg[i]=0;// 读入边并更新度数for(inti=0;i<m;i++){intu,v;scanf("%d%d",&u,&v);deg[u]++;deg[v]++;}// 计算线图的边数longlongans=0;// 结果可能很大，使用 long longfor(inti=1;i<=n;i++){// 累加 C(deg[i], 2)ans+=(longlong)deg[i]*(deg[i]-1)/2;}printf("%lld\n",ans);return0;}

功能分析

1. 输入处理

• 读入顶点数n和边数m。
• 通过循环读入每条边，同时更新相关顶点的度数。

2. 度数统计

• 数组deg[]记录每个顶点的度数，即与该顶点相连的边的数量。
• 对于每条边(u, v)，deg[u]和deg[v]各增加 1。

3. 核心计算

• 遍历所有顶点，对每个顶点i计算组合数( d e g [ i ] 2 ) \binom{deg[i]}{2}(2deg[i]​)。
• 公式deg[i] * (deg[i] - 1) / 2直接计算组合数，避免了阶乘运算。
• 累加所有顶点的组合数得到线图的边数。

4. 输出结果

• 使用%lld格式输出最终结果。

注意事项

• 结果可能超出int范围（最大约10 10 10^{10}1010），必须使用long long。
• 数组大小应略大于最大顶点数（10 5 10^5105），防止越界。
• 输入使用scanf提高效率，适合大数据量。

验证样例

• 样例1：顶点度数分别为 2,2,2,1,1，组合数之和为 1+1+1+0+0=3，与输出一致。
• 样例2：完全图K 5 K_5K5​每个顶点度数为 4，组合数为 6，5 个顶点总和为 30，与输出一致。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}