← 返回题单
题单练习 2025年6月GESP编程题
← 上一题 下一题 →

A5184 | [GESP202506 七级] 线图

来源2025
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定由 $n$ 个结点与 $m$ 条边构成的简单无向图 $G$，结点依次以 $1,2,\dots,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 105 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

  1 2
  1 3
  1 4
  1 5
  2 3
  2 4
  2 5
  3 4
  3 5
  4 5
输出 #2
30
C++ 编辑器
输入
输出