A67241 | 连通图

试题名称：连通图

时间限制： 1.0 s

内存限制：512.0 MB

3.1.1     题目描述

给定一张包含 n 个结点与 m 条边的⽆向图 ，结点依次以 1,2, ...n 编号 ，第 i 条边（ 1 ≤ i ≤ m）连接结点 u_i 与结点 v_i 。如果从一个结点经过若⼲条边可以到达另一个结点 ，则称这两个结点是连通的。

你需要向图中加⼊若⼲条边 ，使得图中任意两个结点都是连通的 。请你求出最少需要加⼊的边的条数。

注意给出的图中可能包含重边与⾃环。

3.1.2     输入格式

第一⾏ ，两个正整数 n, m ，表⽰图的点数与边数。

接下来 m ⾏ ，每⾏两个正整数 u_i , v_i ，表⽰图中一条连接结点 u_i 与结点  v_i 的边。

3.1.3     输出格式

输出一⾏ ，一个整数 ，表⽰使得图中任意两个结点连通所需加⼊的边的最少数量。

3.1.4     样例

3.1.4.1     输入样例 1

4 4

1 2

2 3

3 1

1 4

3.1.4.2     输出样例 1

0

3.1.4.3     输入样例 2

6  4

1  2

2  3

3  1

6  5

3.1.4.4     输出样例 2

2

3.1.5     数据范围

对于 40% 的测试点 ，保证 1 ≤ n ≤ 100 ，1  ≤ m ≤ 100。

对于所有测试点 ，保证 1 ≤ n ≤ 10⁵ ，1  ≤ m ≤ 10⁵ 。