并查集笔记

代码实现：
通过路径压缩把某类节点统统并入根节点，类似于冠状病毒(?

首先把每个节点的父节点设置为他们自己

find函数以及修改父节点代码实现

int findset(int n){
    return fa[n]==n?n:fa[n]=findset(fa[n]);
}

并查集父节点查询与融合操作

int fx=findset(x),fy=findset(y);
            if(fx==fy) continue;//父节点相同说明在同一区间内
            fa[fx]=fy;

启发式合并：额外增加一个siz数组记录在父节点为i的情况下，子节点的个数，当两个区域融合时，让子节点个数少的区域优先被修改

int fx=findset(x),fy=findset(y);
            if(fx==fy) continue;
            if(siz[x]>siz[y])\\保证fx=fy;
            siz[fy]+=siz[fx];

例题:行进路线 - 题目 - Daimayuan Online Judge

#pragma GCC optimize(2)
#pragma GCC optimize(1)
#include
typedef long long ll;
typedef unsigned long long ull;
const ull base=131;
#define MAX 1009
#define PI 3.141592653589793
using namespace std;
ll node[MAX][3],fa[MAX];
int findset(int n){
    return fa[n]==n?n:fa[n]=findset(fa[n]);
}
inline void solve(){
    ll xe,ye;cin>>xe>>ye;
    int time;cin>>time;
    for(int i=1;i<=time;i++){
        cin>>node[i][0]>>node[i][1]>>node[i][2];
    }
    for(int i=0;ii;
    node[0][0]=0;node[0][1]=0;node[0][2]=1;
    for(int i=0;i<=time;i++)
        for(int j=i+1;j<=time;j++){
            if((node[i][0]-node[j][0])*(node[i][0]-node[j][0])+(node[i][1]-node[j][1])*(node[i][1]-node[j][1])<=(node[i][2]+node[j][2])*(node[i][2]+node[j][2])){
                int fx=findset(i),fy=findset(j);
                if(fx==fy) continue;
                fa[fy]=fx;
            }
        }
    int dex=-1;
    for(int i=0;i<=time;i++){
        if((node[i][0]-xe)*(node[i][0]-xe)+(node[i][1]-ye)*(node[i][1]-ye)<=node[i][2]*node[i][2])
                dex=i;
       }
    if(dex!=-1&&findset(0)==findset(dex))
        cout<<1<<endl;
    else
    cout<<0<<endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int sum;cin>>sum;
    while(sum--){
        solve();
    }
}