C++程序题：计算将无向图变为连通图所需添加的最少边数

时间限制：1.0 s
内存限制：512.0 MB

题目描述

给定一张包含n个结点与m条边的无向图，结点依次以1,2,…,n编号，第i条边（1≤i≤m）连接结点u_i与结点v_i。如果从一个结点经过若干条边可以到达另一个结点，则称这两个结点是连通的。你需要向图中加入若干条边，使得图中任意两个结点都是连通的。请你求出最少需要加入的边的条数。注意：给出的图中可能包含重边与自环。

输入格式

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

输出格式

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

样例

样例输入1

样例输出1

样例输入2

样例输出2

数据范围

对于40%的测试点，保证1≤n≤100，1≤m≤100
对于所有测试点，保证1≤n≤10^5，1≤m≤10^5