1498: 村里有个姑娘叫小Jun

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：61 解决：15

题目描述

在Jun小镇上有n个村庄,村庄与村庄之间可能直接相连也可能不直接相连，甚至两个村庄就无法相互到达。
现给n个村庄编号为1-n，对所有村庄,若存在村庄l到村庄r的路径（l就可构建和谐小镇。为了达成这一条件，需要添加多少条路径。

输入

第一行两个整数n,m（n为村庄个数，m为直连边数） 3≤n≤200 000 and 1≤m≤200 000
接下来m行，每一行两个整数表示村庄ai和aj直连。

输出

一个整数

样例输入复制

14 8 1 2 2 7 3 4 6 3 5 7 3 8 6 8 11 12

样例输出复制

1

来源/分类

Baidu
map