POJ 2236 Wireless Network

問題

解法
Union-Find木を使って連結状態的なものを持っておく。
コンピュータpを修理したとき、他の修理されたコンピュータの中で距離d以内のものとuniteする
同じ根を持てば、通信可能である。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
const int MAX_N = 1024;
int N, d;
P a[MAX_N];
int uf[MAX_N];
bool b[MAX_N];
void init(){
	for(int i = 0; i < N; i++){
		uf[i] = i;
		b[i] = false;
	}
}
int get_root(int p){
	if(uf[p] == p) return p;
	int t = get_root(uf[p]);
	return uf[p] = t;
}
bool is_same(int p, int q){
	int s = get_root(p);
	int t = get_root(q);
	return (s==t);
}
void unite(int p, int q){
	int t = get_root(p);
	int s = get_root(q);
	uf[t] = s;
}
void rep(int p){
	b[p] = true;
	for(int i = 0; i < N; i++){
		if(p == i) continue;
		if(!b[i]) continue;
		int t = a[i].first - a[p].first;
		int s = a[i].second - a[p].second;
		if(t * t + s * s <= d * d){
			if(!is_same(p, i))
				unite(p, i);
		}
	}
}
int main(){
	scanf("%d %d", &N, &d);
	for(int i = 0; i < N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		a[i] = P(x, y);
	}
	init();
	char c, op;
	scanf("%c", &c);
	while(scanf("%c", &op) != EOF){
		if(op == 'O'){
			//repairing
			int p;
			scanf("%d", &p);
			rep(p-1);
		}else{
			int p, q;
			scanf("%d %d", &p, &q);
			if(is_same(p-1, q-1))
				puts("SUCCESS");
			else
				puts("FAIL");
		}
		scanf("%c", &c);
	}
	return 0;
}