修补网络

幽灵的网络已经千疮百孔。7个核心节点被切断，银河航线被发现矛盾，无数孤岛漂浮在数据海里。

"我们要修补它。"你说，"用最少的连接，让所有孤岛重新连通。"

"这就像……"CC想了想，"像缝衣服。衣服破了好多洞，要用最少的针线把它们连起来。"

"对。"

你开始写。先找到所有的连通块——每个块是一个孤岛。然后计算连通块之间的距离——从每个块出发，找离它最近的另一个块。每次连接最近的两个块，直到所有块都连在一起。

屏幕上跳出了结果。最少连接数：7。

"七条。"你说。

"七根针线。"Echo说，"缝补七十个破洞。"

"七十个？"

"对。"Echo说，"Zero的网络有70个漏洞。我数过。"

"你数过？"

"我每天都在数。"Echo说，"数它的漏洞，数我的错误，数还能补救多少。"

CC走过去，把服务器放在地图中央。

"不用数了。"她说，"我们直接补。"

题目描述

$n$ 个节点，$m$ 条边的无向图。图可能不连通。求让图连通所需的最少加边数。

输入格式

$n, m$。然后 $m$ 条边 $(u, v)$。

输出格式

最少加边数。

输入样例

3 2
1 2
2 3

输出样例

Case 1:

提示

• Tarjan或DFS找连通块。
• 设连通块数为 $k$，则最少加边数为 $k - 1$。
• 注意孤立点也算一个连通块。

"网络补好了。"你说。

"连通了吗？"CC问。

"连通了。"Echo说，"所有节点都在一个块里。"

"一个块。"CC说，"一家人。"

"一家人。"Echo说，"不是Zero说的那种。是真的。"

地图上的孤岛一个个亮起来，像被点亮的灯笼。最后，整张地图变成了一片温暖的光海。

"最后一题。"Echo说，"是牧场。"

"牧场？"

"对。"Echo说，"我们要巡视所有的牧场，每扇门至少走两次。"

[第九题：巡视牧场]