POJ 2236 Wireless Network(并查集裸题)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 1005;
int pre[MAXN];
struct Node{
  double x,y;
}Edge[MAXN];
bool vis[MAXN];
int n,d,m;
char ch;

double dist(Node a,Node b){
  double temp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  return sqrt(temp);
}

void init(){
  for(int i=1;i<=n;i++){
    pre[i] = i;
  }
}

int Find(int x){
  if(x != pre[x]){
    pre[x] = Find(pre[x]);
  }
  return pre[x];
}

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy && dist(Edge[x],Edge[y]) <= d){
    pre[fy] = fx;
  }
}

int main()
{
  memset(vis,0,sizeof(vis));
  scanf("%d%d",&n,&d);
  init();
  for(int i=1;i<=n;i++){
    scanf("%lf%lf",&Edge[i].x,&Edge[i].y);
  }
  while(cin>>ch){             // 用cin比scanf方便
    if(ch == 'O'){
      scanf("%d",&m);
      vis[m] = 1;
      for(int i=1;i<=n;i++){
        if(vis[i] && i != m){
          merge(m,i);
        }
      }
    }
    else{
      int a,b;
      scanf("%d%d",&a,&b);
      if(Find(a) == Find(b)){
        printf("SUCCESS\n");
      }
      else{
        printf("FAIL\n");
      }
    }
  }
  return 0;
}