加边的无向图-题解

有n个点，m条边的无向图，求至少加多少条边使任意两个点互通。
先利用并查集找到连通块，最后只要在各个连通块之间加边，数量等于连通块数-1.
求连通块数量：只要某个点的“祖先”是它自己，那么它就是一个连通块的“祖先”，遍历一遍所有的点，有多少这样的点就有多少个连通块。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+10;
int fa[maxn];
int findfa(int x)
{
    return (x==fa[x])?x:fa[x]=findfa(fa[x]);
}
int main()
{
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(m--)
    {
        int i,j;
        cin>>i>>j;
        int u=findfa(i);
        int v=findfa(j);
        if(u!=v) fa[u]=v;
    }
    for(int i=1;i<=n;i++)
    {
        if(findfa(i)==i) ans++;
    }
    cout<<ans-1<<endl;
    return 0;
}

谢谢阅读！
祝你学习愉快！