← 返回题目
题库练习 线图
← 上一题 下一题 →

A71911 | 线图

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

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

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

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

对于无向图 G 中两条不同的边(u_1，v_1 )，(u_2，v_2 )，若存在 G 中的结点同时连接这两条边（即 u_1，v_1 之一与u_2，v_2之一相同），则在线图 L(G) 中加入一条无向边，连接 (u_1，v_1 )，(u_2，v_2 ) 在线图中对应的结点。

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

输入格式

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

接下来 m 行，每行两个正整数 u_i，v_i，表示 G 中连接 u_i，v_i 的一条无向边。

输出格式

输出共一行，一个整数，表示线图 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
C++ 编辑器
输入
输出