[数据结构与算法]周周的舟舟 (并查集 思维

添加链接描述

#include<bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int>mp,fa;
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void merge(int a,int b){
    fa[b]=a;
}
double get_dist(double a,double b,double c,double d){
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
signed main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int d,q;
    cin>>d>>q;
    int res=0;
    while(q--){
        res++;
        int x,y;
        cin>>x>>y;
        mp[x]=y;
        fa[x]=x;
        for(int i=x-d;i<=x+d;i++){
            if(mp.find(i)==mp.end())continue;
            if(mp[i]&&i!=x){
                if(get_dist(i,mp[i],x,mp[x])<=d){
                    if(find(x)!=find(i)){
                        res--;
                        merge(find(x),find(i));
                    }
                }
            }
        }
        cout<<res<<"\n";
    }

    return 0;
}