N. 星际连通图

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一张无向图，共有 $n$ 个点、 $m$ 条边，点编号为 $1$ 到 $n$ 。图中可能存在重边和自环。

现在你可以向图中加入若干条新边，目标是让整张图变成连通图，也就是任意两个点之间都存在路径可以互相到达。

请你求出最少需要添加多少条新边。

第一行两个整数 $n,m$ 。

接下来 $m$ 行，每行两个整数 $u,v$ ，表示一条无向边。

输出一个整数，表示最少需要添加的新边数量。

4 2
1 2
3 4

样例 1 解释：

原图中共有两个连通块：{1,2} 和 {3,4}，因此只需要再加 $1$ 条边就能把整张图连起来。

样例 2 解释：

自环和重边都不会改变连通性。原图中共有三个连通块：{1,2}、{3,4} 和 {5}，因此最少还需要添加 $2$ 条边。

对于所有测试点，保证 $1 \le n,m \le 10^5$ 。