编程题 第 1 题25 分
线图
时间限制 1 秒 · 内存限制 512 MB
题目描述
给定由 个结点与 条边构成的简单无向图 ,结点依次以 编号。简单无向图意味着 中不包含重边与自环。 的线图 通过以下方式构建:
- 初始时线图 为空。
- 对于无向图 中的一条边,在线图 中加入与之对应的一个结点。
- 对于无向图 中两条不同的边 ,若存在 中的结点同时连接这两条边(即 之一与 之一相同),则在线图 中加入一条无向边,连接 在线图中对应的结点。
请你求出线图 中所包含的无向边的数量。
输入格式
第一行,两个正整数 ,分别表示无向图 中的结点数与边数。
接下来 行,每行两个正整数 ,表示 中连接 的一条无向边。
输出格式
输出共一行,一个整数,表示线图 中所包含的无向边的数量。
样例 1
输入
5 4 1 2 2 3 3 1 4 5
输出
3
样例 1 解释
原图 的边为 、、、,对应线图 中的结点 。其中 两两相连(共 条边), 为孤立结点:
G L(G)
1 4 e12 ──── e13 e45
/ \ \ \ /
2 ─ 3 5 \ /
e23
样例 2
输入
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
输出
30
数据范围
对于 的测试点,保证 ,。
对于所有测试点,保证 ,。