题目链接

任意点 加边的无向图

题目思路

都是通过用并查集来寻找是否各点是否关联，通过merge处理之后寻找是否fa[i]==i，从而确定有几个未关联的点集

代码实现

//任意点
#include<bits/stdc++.h>
using namespace std; 
const int Max=1e5;
int n,sum=0;
int fa[Max];
struct node{
    int x,y;
}a[Max];
void init()
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
}
int find(int a)
{
    if(fa[a]!=a)
    {
        fa[a]=find(fa[a]);
    }
    return fa[a];
}
void merge(int a,int b)
{
    int faa=find(a),fab=find(b);
    if(faa!=fab)
    {
        fa[faa]=fab;
    }
}
int main()
{
    cin>>n;
    sum=0;
    init();
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            if(a[i].x==a[j].x||a[i].y==a[j].y)
                merge(i,j);
    for(int i=1;i<=n;i++)
        if(fa[i]==i)
            sum++;
    cout<<sum-1<<endl;
    return 0;
}

//加边的无向图
#include<bits/stdc++.h>
using namespace std;
const int Max=1e5;
int n,m;
int ft[Max];
void init()
{
    for(int i=1;i<=n;i++)
        ft[i]=i;
}
int find(int x)
{
    return ft[x]==x?x:ft[x]=find(ft[x]);
}
void merge(int x,int y)
{
    int a=find(x),b=find(y);
    ft[b]=a;
}
int main()
{
    cin>>n>>m;
    init();
    int ii,jj,sum=0;
    for(int i=1;i<=m;i++)
    {
        cin>>ii>>jj;
        merge(ii,jj);
    }
    for(int i=1;i<=n;i++)
    {
        if(ft[i]==i)
        {
            sum++;
        }
    }
    cout<<sum-1<<endl;
    return 0;
}