問題は以下のように言い換えることができます。

$N$ 頂点 $M$ 辺の無向グラフ $G$ があり、 $i$ 番目の辺は$A_i$ 番目の頂点と $B_i$ 番目の頂点を結んでいます。
$G$ を連結にするために最低でも何本の辺を追加する必要があるでしょうか。

この問題を解くにあたり、連結成分の数に着目します。
例えば連結成分が $1$ 個の場合、既に条件は満たされているため、答えは $0$ です。
また、連結成分が $2$ 個の場合、 $2$ つの連結成分から一つずつ選んだ頂点の間に辺を追加することで条件が満たされるので、答えは $1$ です。

このように考えると、異なる $2$ つの連結成分から $1$ つずつ頂点を選び、その $2$ 頂点を結ぶ辺を追加することで連結成分の数が $1$ 減ることが分かります。
よって、答えは ( $G$ の連結成分の数 ) $-1$ となります。

グラフの連結成分の数を求めるには、いくつかの手法があります。

Union-Find を使う場合

Union-Find とは各グループをそれぞれ $1$ つの木としてみなし、 $2$ 頂点が同グループかを $2$ 頂点が属する木の根にあたる頂点が同じかで判定するデータ構造です。
C++ の場合、atcoder/all もしくは atcoder/dsu を include することで使える ACLの dsu を用いると容易に実装できます。
Union-Find そのものの説明としては以下のページにあるスライドが参考になります。
参考記事

深さ優先探索や幅優先探索 を使う場合

DFS や BFS と呼ばれる手法です。
DFS は頂点 $i$ から可能な限り進み、進めなくなったら $1$ つ前の頂点に戻り進めるか判断するという頂点を調べるアルゴリズムです。
実装は再帰関数を用意するとよいでしょう。

BFS は頂点 $i$ から $1$ つの辺でいける頂点を列挙、 $2$ つの辺でいける頂点を列挙... という風に頂点を調べるアルゴリズムです。
実装は queue などを用意するとよいでしょう。

どちらの場合でも、最初の処理を呼び出した回数が連結成分の数にあたります。
参考記事

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
  int n,m;
  cin>>n>>m;
  
  //n頂点のグラフgを用意する
  dsu g(n);
  
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    
    //入力の1がgでの0に対応
    a--;b--;
    
    //辺を追加する
    g.merge(a,b);
  }
 
  //連結成分の数-1が答え
  int ans=g.groups().size()-1;
  
  cout<<ans<<endl;
}