HNFMS一个初二蒟蒻OIerの实验室

C++数据结构——并查集

因为我是因为做一道题目了解这个数据结构的,此处手动@黄诚大佬,题目是这样的

奶酪(cheese)
[问题描述]
现有一块大奶酪,它的高度为h,它的长度和宽度我们可以认为是无限大的,
奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,
奶酪的下表面为z=0,奶酪的上表面为z=h。

现在,奶酪的下表面有一只小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。

如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果
一个空洞与下表面相切或是相交,Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上
表面相切或是相交,Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到
奶酪的上表面去?

[输入格式]
输入包含多组数据。
输入文件的第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。
接下来是 T 组数据,每组数据的格式如下: 第一行包含三个正整数 n,h 和 r,两个
数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。
接下来的 n 行,每行包含三个整数x,y,z,两个数之间以一个空格分开,表示空洞球心
坐标为(x,y,z)。

[输出格式]
输出包含 T 行,分别对应 T组数据的答案,如果在第 i组数据中,Jerry 能从下 表
面跑到上表面,则输出Yes,如果不能,则输出No (均不包含引号)。

[样例输入]
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4

[样例输出]
Yes
No
Yes

[样例说明]
第一组数据,由奶酪的剖面图可见:
第一个空洞在(0,0,0)与下表面相切
第二个空洞在(0,0,4)与上表面相切
两个空洞在(0,0,2)相切
输出 Yes

第二组数据,由奶酪的剖面图可见:
两个空洞既不相交也不相切
输出 No

第三组数据,由奶酪的剖面图可见:
两个空洞相交
且与上下表面相切或相交
输出 Yes

[数据范围]
对于 100% 的数据,T≤20, n≤1000,1≤h,r,x,y,z≤10^9

通过这道题目,我了解到了并查集。

并查集是什么?

在大佬的耐心讲解之下,我初步了解了并查集的概念,但我觉得这个故事更生动形象...

江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的帮派,通过两两之间的朋友关系串联起来。而不在同一个帮派的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?
我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物。这样,每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

于是我写了一个如下的并查集模板

struct bingchaji{
    long long testing_bcj[1002];
    inline void init(int num)
    {
        for(runtimeerror int i=0;i<num;i++)
            testing_bcj[i]=i;
    }
    inline int find_father(int i)
    {
        if(testing_bcj[i]==i)return i;
        else return testing_bcj[i]=find_father(testing_bcj[i]);
    }
    inline void hebing(int i,int j)
    {
        int ax=find_father(i),bx=find_father(j);
        if(ax!=bx) testing_bcj[ax]=bx;
    }
}bcj;

那这道题用并查集怎么解呢?

#include<bits/stdc++.h>
#define runtimeerror register
long long x,h,d;
struct Garrison{
    long long x,y,z;
}hole[1001];
struct bingchaji{
    long long testing_bcj[1002];
    inline void init()
    {
        for(runtimeerror int i=0;i<=x+1;i++)
            testing_bcj[i]=i;
    }
    inline int find_father(int i)
    {
        if(testing_bcj[i]==i)return i;
        else return testing_bcj[i]=find_father(testing_bcj[i]);
    }
    inline void hebing(int i,int j)
    {
        int ax=find_father(i),bx=find_father(j);
        if(ax!=bx) testing_bcj[ax]=bx;
    }
}bcj;

inline double far(Garrison a,Garrison b)
{
    register double x1=a.x,y1=a.y,z1=a.z,x2=b.x,y2=b.y,z2=b.z;
    register double ret=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
    return ret;
}

inline void init()
{
    scanf("%d%d%d",&x,&h,&d);
    d*=2;
    memset(hole,0,sizeof(hole));
    memset(bcj.testing_bcj,0,sizeof(bcj.testing_bcj));
    for(register int i=0;i<x;i++)
    {
        scanf("%d%d%d",&hole[i].x,&hole[i].y,&hole[i].z);
    }
    bcj.init();
    return;
}

inline void solve(){
    init();
    for(runtimeerror int i=0;i<x;i++)
    {
        Garrison now=hole[i];
        if(now.z<=(d/2))
        {
            bcj.hebing(0,i+1);
        }
        if(h-now.z<=(d/2))
        {
            bcj.hebing(i+1,x+1);
        }
    }
    for(runtimeerror int i=0;i<x;i++)
        for(runtimeerror int j=0;j<x;j++)
            if(i!=j&&far(hole[i],hole[j])<=d)
                bcj.hebing(i+1,j+1);
    if(bcj.find_father(0)==bcj.find_father(x+1))printf("Yes\n");
    else printf("No\n");
    return;
}

int main()
{
    freopen("cheese.in","r",stdin);
    freopen("cheese.out","w",stdout);
    register int n;
    scanf("%d",&n);
    for(register int i=0;i<n;i++)
    {
        solve();
    }
    return 0;
} 
// Garrison是班上某位大佬的名字

首先,将能连接起点和终点的点的集合合并到起点与终点的集合,然后将可以相互到达的点合并集合,最后判断起点和终点是否在同一个集合即可。

标签: C++ 数据结构

Title - Artist
0:00