蓝桥杯复习之并查集

并查集是一种代码简短的，主要用于解决一些元素分组问题的数据结构。

它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

题目链接：https://www.acwing.com/problem/content/530/
 

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
using ll= long long;
struct P{
    ll x,y,z;
}p[N];
int f[N];
int n,h,r;

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


int main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>h>>r;
        for(int i=0;i<=n + 1;i++)
            f[i]=i;
        for(int i=1;i<=n;i++){
            cin>>p[i].x>>p[i].y>>p[i].z;
            if(p[i].z<=r)f[find(i)]=find(0);//合并操作无所谓左右

            if(p[i].z+r>=h)f[find(i)]=find(n+1);
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                ll dx = p[i].x - p[j].x;
                ll dy = p[i].y - p[j].y;
                ll dz = p[i].z - p[j].z;

                if (dx * dx + dy * dy + dz * dz <= 4 * (ll)r * r)
                    f[find(i)] = find(j); 
            }
        }
        if(find(0)==find(n+1))cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}