一道简单的并查集


大意:
给出网点的坐标和网点间可以连接的最大距离,有开启网点和检测网点操作,问检测网点时能否接通。
(只要在检测的网点有在最大距离范围内已被开启的就成功)
思路:
题目就是昨天的基本的模板的小改动。
不是所有点都连接-->要通过两点之间的Distance(Point a,Point b)来判断可否union
不开启的网点不能访问-->用ready[]存储开启的网点,检测时在ready[]数组中查找才行。

代码在此

#include <iostream>
#include <math.h>
#define MaxSize 1010
using namespace std;

struct Point{
    int x,y;
}P[MaxSize];

int parent[MaxSize];
int ready[MaxSize];
int n;
double d;

int Root(int a){
    if(a != parent[a]) parent[a] = Root(parent[a]);
    return parent[a];
}

void union_(int x,int y){
    int x_root = Root(x);
    int y_root = Root(y);
    if(x_root != y_root) {
        parent[x_root] = y_root;
    }
}

double Dis(Point a,Point b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}

int main()
{
    cin>>n>>d;
    for(int i = 1;i <= n;i++){
        parent[i] = i;
        cin>>P[i].x>>P[i].y;
    }    
    char c[4];int node;
    int num_ready = 1;
    while(~scanf("%s %d",c,&node)){
        if(c[0] == 'O'){
            for(int i = 1;i < num_ready;i++){
                if(Dis(P[ready[i]],P[node]) <= d){
                    union_(ready[i],node);
                }
            }
            ready[num_ready++] = node;
        }
        else{
            int check;
            cin>>check;
            if(Root(check) == Root(node)) printf("SUCCESS\n");
            else printf("FAIL\n");
        }
    }
    return 0;
    
} 


开始时我的代码思路很混乱,查了一些博客后发现这样写会很简洁~

今天的c++期末真是坑,题目全是bug
一道题样例给的输出和题目描述不一样,一道题define了PI = 3.14,但是如果用这个PI就错了
最后还好都AC了,有惊无险吧。

这两天总头晕冒冷汗。

明天考模电啊,今天一天学了整整一本书的模电,头疼的很
希望明天能正常发挥,睡觉去了!

Last modification:June 29th, 2020 at 11:10 pm
请赏我杯奶茶,让我快乐长肉