Wireless Network(并查集)

发布于 2020-09-04  0 次阅读


题目大意:

Wireless Network
在二维平面上,给你n个点,和一个距离d
O+数字表示激活该台电脑
S+数字+数字,表示连通两台电脑,在d距离之内就能连通,能连通输出SUCCESS,不行就输出FAIL

思路:

每次有电脑被激活的时候,就遍历一次可以连接到的电脑,对于同一个集合(即连接了的电脑)使用并查集维护一下就可以了

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e3+9;
int n, d, idx1, idx2;
int fa[N];
char s;
struct node{
    int x, y;
    bool flag;
}a[N];

int dis(node a, node b){
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

int find(int u){                  
	if(fa[u]==u)	return u;
	return fa[u]=find(fa[u]);
}

void link(int q){
    int now=find(q);
    for(int i=1; i<=n; i++){
        if(a[i].flag && dis(a[q],a[i])<=d*d){
            int next=find(i);
            fa[next]=now;
        }
    }
    return ;
}

void solve(){
    cin>>n>>d;
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=n; i++){
        cin>>a[i].x>>a[i].y;
        a[i].flag=false;
    }
    while(cin>>s){
        if(s=='O'){
            cin>>idx1;
            a[idx1].flag=true;
            link(idx1);
        }
        else{
            cin>>idx1>>idx2;
            if(find(idx1)==find(idx2))  cout<<"SUCCESS"<<endl;
            else    cout<<"FAIL"<<endl;
        }
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生