A27107. 线图
填空题
困难
知识点
题目描述
线图
题目描述
给定由n个结点与 m条边构成的简单无向图 G，结点依次以 1,2,……,n编号。简单无向图意味着 G中不包含重边与自环。G的线图 L(G)通过以下方式构建:
初始时线图 L(G)为空。
对于无向图 G中的一条边，在线图L(G)中加入与之对应的一个结点。
对于无向图G中两条不同的边(u1,v1),(u2,v2)，若存在G中的结点同时连接这两条边(即u1,v1之一与u2,v2之一相同)，则在线图L(G)中加入一条无向边，连接(u1,v1),(u2,v2)在线图中对应的结点。
请你求出线图工L(G)中所包含的无向边的数量。
输入格式
第一行，两个正整数 n,m，分别表示无向图G中的结点数与边数。
接下来 m 行，每行两个正整数 ui,vi，表示 G 中连接 ui,vi的一条无向边。
输出格式
输出共一行，一个整数，表示线图L(G)中所包含的无向边的数量。
样例
输入样例 1
5 4
1 2
2 3
3 1
4 5输出样例 1
3输入样例 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% 的测试点，保证1≤n≤500，1≤m≤500。
对于所有测试点，保证 1≤n≤105，1≤m≤ 105。
参考答案
#include <cstdio>
using namespace std;
const int N= 1e5 +5;
int n, m, deg[N];
long long ans;
int main(){
scanf("%d%d"，&n, &m);
while(m--){
int u, v;
scanf("%d%d"，&u,&v);
deg[u]++;
deg[v]++;
}
for(int i=1;i<= n; i++)
ans += 11l*deg[i]*(deg[i]-1)/ 2;
printf("%lld\n",ans);
return 0;
}
上一题
下一题