POJ 2236 Wireless Network (并查集)

浏览数：23 / 时间：2015年06月09日

思路及大意：给你n个电脑的坐标，然后是两种操作，‘o‘是修复某台电脑，’s‘是询问p，q两台电脑是否能够连接。

计算每次修复好的电脑与之前修复好的电脑之间的距离，若在d内，则将他们放入一个集合中；

若p，q两台电脑在一个集合中，则表示他们可以连接。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000+10
using namespace std;

int x[N],y[N],v[N];
int dist(int i,int j)
{
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int f[N];
void Init(int n)
{
    for(int i=0;i<n;i++)
        f[i]=i;
}
int Find(int x)
{
    return x==f[x]?x:f[x]=Find(f[x]);
}
void Merge(int a,int b)
{
    int ra=Find(a),rb=Find(b);
    if(ra==rb){
        return ;
    }else{
        f[rb]=ra;
    }
}
int main()
{
    int n,d;
    scanf("%d %d",&n,&d);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&x[i],&y[i]);
    Init(n);
    memset(v,0,sizeof(v));
    char str[5];
    while(scanf("%s",str)!=EOF)
    {
        if(str[0]=='O')
        {
            int k;
            scanf("%d",&k);
            v[k]=1;
            for(int i=1;i<=n;i++)
            {
                if(v[i] && dist(k,i)<=d*d)
                    Merge(k,i);
            }
        }
        else
        {
            int a,b;
            scanf("%d %d",&a,&b);
            int ra=Find(a),rb=Find(b);
            if(ra==rb) puts("SUCCESS");
            else puts("FAIL");
        }
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

POJ 2236 Wireless Network (并查集)