poj 2236 Wireless Network(并查集)

题目链接：poj 2236 Wireless Network

题目大意：在一次地震过后，机房的电脑全部损坏了，给出n台电脑的坐标，以及有的连接线的长度d，现在进行若干次操作，O x 表示将x号电脑修好，那么就可以与离这台电脑的距离小于d并且已经修好过的电脑相连；S x 检查x和y是否联通。

解题思路：首先将每台电脑可以联通到的电脑先预处理出来，然后在开一个标记数组表示哪些电脑被修好了。每修好一个电脑后就将该电脑与周围可以联通并且修好的电脑联通。

#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 1005;
const double eps = 1e-9;

struct point {
	double x, y;
}p[N];
int n, g[N][N], c[N], f[N], v[N];
double d;

int getfar(int x) {
	return x == f[x] ? x : f[x] = getfar(f[x]);
}

double dist (double x, double y) {
	return sqrt(x*x + y*y);
}

void init () {

	memset(v, 0, sizeof(v));
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		scanf("%lf%lf", &p[i].x, &p[i].y);
		for (int j = 1; j < i; j++) {
			double tmp = dist(p[i].x-p[j].x, p[i].y-p[j].y);
		   if (d - tmp > -eps) {
				g[i][c[i]++] = j;
				g[j][c[j]++] = i;
			}
		}
	}
}

int main () {
	scanf("%d%lf", &n, &d);

	init ();

	int a, b;
	char str[10];
	while (scanf("%s", str) == 1) {
		if (str[0] == 'O') {

			scanf("%d", &a);
			v[a] = 1;
			int p = getfar(a);;
			for (int i = 0; i < c[a]; i++) {
				int u = g[a][i];

				if (v[u] == 0) continue;

				int q = getfar(g[a][i]);
				if (p != q)
					f[q] = p;
			}
		} else {
			scanf("%d%d", &a, &b);
			int p = getfar(a), q = getfar(b);
			printf("%s\n", p == q ? "SUCCESS" : "FAIL");
		}
	}
	return 0;
}