P1536 村村通

为使整张图连通，还应增加的边数为连通块数减一

const int N=5010;
int p[N];
int n,m,q;

int find(int x)
{
    if(x != p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++) p[i]=i;

        while(m--)
        {
            int a,b;
            cin>>a>>b;
            int pa=find(a);
            int pb=find(b);
            p[pa]=pb;
        }

        int cnt=0;
        for(int i=1;i<=n;i++)
            if(p[i] == i)
                cnt++;

        cout<<cnt-1<<endl;
    }


    //system("pause");
}

P1536 村村通

原文：https://www.cnblogs.com/fxh0707/p/13601070.html