加边的无向图

题目描述：

链接：https://ac.nowcoder.com/acm/problem/14685

给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达~

输入描述：

第一行两个正整数 n 和 m 。接下来的m行中，每行两个正整数 i 、 j ，表示点i与点j之间有一条无向道路。

输出描述：
输出一个整数，表示答案

数据范围：对于100%的数据，有n,m<=100000。

solution：

先将已有的边通过并查集形成一棵最小生成树
再找出树中已有的一个点与其它点进行比较，判断是否在树中，不在则进行合并操作

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100005],s=0,u,v;
int f1(int x)
{
    return f[x]==x?x:f[x]=f1(f[x]);
}
void Union(int x,int y)
{
    int u=f1(x),v=f1(y);
    f[u]=v;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        if(f1(u)!=f1(v))
            Union(u,v);
    }
    int k=0;
    for(int i=1;i<=n;i++)
    {
        if(f[i]!=i)
        {
            k=i;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(f1(i)!=f1(k))
        {
            Union(i,k);
            s++;
        }
    }
    cout<<s;
}