题目连接

题意:一张图上分布着n台坏了的电脑,并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网,也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x,给出操作“S x y”,请你判断x和y在此时有没有连接上。

分析:把每次修好的电脑能到达的都扔进一个集合里,然后直接判断即可。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-9
#define N 1010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct node
{
int x,y;
}p[N];
int fa[N],vis[N];
int dist(node a,node b)
{
return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
int n;
int d;
while(scanf("%d%d",&n,&d)>)
{
for(int i=;i<=n;i++)fa[i]=i,vis[i]=;
for(int i=;i<=n;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
char op[];
int x,y;
while(scanf("%s",op)>)
{
if(op[]=='O')
{
scanf("%d",&x);
vis[x]=;
for(int i=;i<=n;i++)
{
if(vis[i]&&dist(p[i],p[x])<=d*d)
{
int py=find(i);
int px=find(x);
fa[py]=px;
}
}
}
else
{
scanf("%d%d",&x,&y);
if(find(x)==find(y))puts("SUCCESS");
else puts("FAIL");
}
}
}
}
04-23 17:02